알고리즘 문제 해결 과정에서 흔히 마주치는 두 가지 유형의 문제, 즉 슬라이딩 윈도우 내의 최댓값을 찾는 문제와 데이터셋에서 빈도수가 높은 상위 K개의 요소를 추출하는 문제에 대해 다룹니다. 각 문제에 대한 효과적인 해결 전략과 함께 C++ 구현 예시를 제시합니다.
슬라이딩 윈도우 최댓값 (LeetCode 239번)
주어진 정수 배열 nums와 정수 k가 있을 때, 크기 k의 슬라이딩 윈도우가 배열의 가장 왼쪽부터 가장 오른쪽으로 이동합니다. 각 윈도우가 이동할 때마다 윈도우 내의 최댓값을 구해야 합니다.
이 문제는 단조 큐 (Monotonic Deque)를 활용하여 효율적으로 해결할 수 있습니다. 단순하게 윈도우 내의 모든 요소를 매번 탐색하거나 정렬하는 방식은 비효율적입니다. 윈도우가 이동할 때마다 최댓값을 빠르게 갱신하려면, 윈도우 내에서 잠재적인 최댓값 후보들을 순서대로 유지하는 자료구조가 필요합니다.
단조 큐는 다음과 같은 특성을 가집니다:
- 큐의 앞(front)에는 항상 현재 윈도우 내의 최댓값(또는 그 인덱스)이 위치합니다.
- 큐 내의 요소들은 내림차순으로 정렬된 상태를 유지합니다.
- 새로운 요소가 윈도우에 진입할 때, 이 요소보다 작거나 같은 값들은 큐의 뒤(back)에서 모두 제거됩니다. 이는 새로운 요소가 더 큰 값이라면 이전의 작은 값들은 더 이상 최댓값이 될 가능성이 없기 때문입니다.
- 윈도우를 벗어나는 요소가 큐의 앞에 있을 경우, 해당 요소는 큐의 앞(front)에서 제거됩니다.
#include <vector>
#include <deque>
class WindowMaxFinder {
public:
// 주어진 배열과 윈도우 크기에 대해 슬라이딩 윈도우의 최댓값들을 반환합니다.
std::vector<int> findSlidingWindowMaximum(const std::vector<int>& dataArray, int windowSize) {
std::deque<int> monotonicDeque; // 단조 감소 큐 (값을 저장)
std::vector<int> maxValues; // 각 윈도우의 최댓값을 저장할 벡터
// 첫 번째 윈도우 (0 ~ windowSize-1) 처리
for (int i = 0; i < windowSize; ++i) {
// 새로 들어오는 값보다 작거나 같은 값들은 큐의 뒤에서 제거
while (!monotonicDeque.empty() && dataArray[i] >= monotonicDeque.back()) {
monotonicDeque.pop_back();
}
monotonicDeque.push_back(dataArray[i]);
}
// 첫 번째 윈도우의 최댓값 저장
maxValues.push_back(monotonicDeque.front());
// 나머지 윈도우 이동 처리
for (int i = windowSize; i < dataArray.size(); ++i) {
// 윈도우를 벗어나는 요소가 큐의 앞에 있다면 제거
// (여기서는 값이 같더라도, 윈도우에서 나가는 값과 큐의 front가 같으면 제거)
if (dataArray[i - windowSize] == monotonicDeque.front()) {
monotonicDeque.pop_front();
}
// 새로 들어오는 값 처리 (이전과 동일)
while (!monotonicDeque.empty() && dataArray[i] >= monotonicDeque.back()) {
monotonicDeque.pop_back();
}
monotonicDeque.push_back(dataArray[i]);
// 현재 윈도우의 최댓값 저장
maxValues.push_back(monotonicDeque.front());
}
return maxValues;
}
};
상위 K개 빈도 요소 (LeetCode 347번)
주어진 정수 배열 nums에서 가장 빈번하게 나타나는 상위 K개의 요소를 찾아야 합니다. 예를 들어, nums = [1,1,1,2,2,3]이고 k = 2라면, [1,2]가 반환되어야 합니다.
이 문제는 두 단계로 접근할 수 있습니다:
- 빈도수 계산: 배열의 각 요소가 몇 번 나타나는지 빈도수를 계산합니다. 이는 해시 맵 (Hash Map 또는
std::unordered_map)을 사용하여 효율적으로 수행할 수 있습니다. - 상위 K개 추출: 계산된 빈도수를 바탕으로 상위 K개의 요소를 추출합니다. 우선순위 큐 (Priority Queue), 특히 최소 힙(Min-Heap)을 사용하면 이 과정을 효율적으로 처리할 수 있습니다. 크기 K를 유지하는 최소 힙에 빈도수와 함께 요소를 저장합니다. 새로운 요소가 들어왔을 때, 해당 요소의 빈도수가 힙의 루트(가장 작은 빈도수)보다 크면 루트를 제거하고 새 요소를 삽입합니다. 힙의 크기가 K를 초과하면 항상 가장 작은 빈도수를 가진 요소를 제거하여 K개의 가장 빈번한 요소만 유지합니다.
#include <vector>
#include <map> // Or unordered_map for potentially faster average case
#include <queue> // For priority_queue
#include <utility> // For std::pair
class TopKFrequentElements {
private:
// 빈도수를 기준으로 최소 힙을 구성하기 위한 사용자 정의 비교자
struct FrequencyComparator {
bool operator()(const std::pair<int, int>& itemA, const std::pair<int, int>& itemB) {
// 두 번째 원소(빈도수)를 기준으로 비교. itemA의 빈도수가 itemB보다 크면 false (Min-Heap이 됨)
return itemA.second > itemB.second;
}
};
public:
// 배열에서 상위 K개 빈도 요소를 찾아서 반환합니다.
std::vector<int> findTopKFrequent(const std::vector<int>& numbers, int k_count) {
std::map<int, int> frequencyMap; // 각 숫자의 빈도수를 저장 (std::map 대신 std::unordered_map 사용 가능)
for (int num : numbers) {
frequencyMap[num]++;
}
// 최소 힙 (빈도수를 기준으로)
// 힙에는 {숫자, 빈도수} 쌍이 저장됩니다.
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
FrequencyComparator> minHeap;
// 맵의 모든 요소를 순회하며 최소 힙에 삽입 및 관리
for (const auto& entry : frequencyMap) {
minHeap.push(entry);
// 힙의 크기가 k_count를 초과하면 가장 빈도수가 낮은 요소 (힙의 루트)를 제거
if (minHeap.size() > k_count) {
minHeap.pop();
}
}
// 힙에 남아있는 K개의 요소들을 결과 벡터에 추가
std::vector<int> topKElements;
while (!minHeap.empty()) {
topKElements.push_back(minHeap.top().first);
minHeap.pop();
}
return topKElements;
}
};