C++ STL set을 활용해 크기 K의 모든 부분 배열 최댓값 구하기

이 튜토리얼에서는 C++ STL의 set 컨테이너를 활용하여 크기가 K인 모든 부분 배열의 최댓값을 구하는 방법을 살펴보겠습니다.

문제 개요

크기가 N인 배열과 정수 K가 주어집니다. 우리의 과제는 연속된 K개의 요소로 구성된 각 부분 배열에서 최댓값을 찾아내고, 이 값들을 모두 더한 뒤 결과를 출력하는 것입니다.

예를 들어 배열이 {4, 10, 54, 11, 8, 7, 9}이고 K가 3이라면 각 윈도우의 최댓값은 다음과 같습니다.

• {4, 10, 54} → 최댓값 54
• {10, 54, 11} → 최댓값 54
• {54, 11, 8} → 최댓값 54
• {11, 8, 7} → 최댓값 11
• {8, 7, 9} → 최댓값 9

따라서 최종 결과는 54 + 54 + 54 + 11 + 9 = 182입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
//각 부분 배열 최댓값들의 합을 반환하는 함수
int maxOfSubarrays(int arr[], int n, int k){
    set<pair<int, int> > q;
    set<pair<int, int> >::reverse_iterator it;
    //첫 번째 윈도우의 요소들을 set에 삽입
    for (int i = 0; i < k; i++) {
        q.insert(pair<int, int>(arr[i], i));
    }
    int sum = 0;
    for (int j = 0; j < n - k + 1; j++) {
        it = q.rbegin();
        sum += it->first;
        q.erase(pair<int, int>(arr[j], j));
        q.insert(pair<int, int>(arr[j + k], j + k));
    }
    return sum;
}
int main(){
    int arr[] = { 4, 10, 54, 11, 8, 7, 9 };
    int K = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxOfSubarrays(arr, n, K);
    return 0;
}

실행 결과

182

동작 원리

이 알고리즘은 슬라이딩 윈도우(sliding window) 기법을 기반으로 동작합니다.

1. (값, 인덱스) 쌍 저장: set에 pair 형태로 요소를 저장합니다. 인덱스를 함께 저장하면 값이 같은 요소라도 구분할 수 있어, 윈도우에서 벗어난 정확한 요소만 제거할 수 있습니다.
2. 자동 정렬 유지: set은 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)로 구현되어 있어, 요소가 삽입·삭제될 때마다 항상 정렬된 상태가 유지됩니다.
3. 최댓값 조회: 역방향 반복자 rbegin()을 사용하면 set에서 가장 큰 원소, 즉 현재 윈도우의 최댓값을 O(log K) 시간에 얻을 수 있습니다.
4. 윈도우 이동: 한 칸씩 이동할 때마다 가장 왼쪽 요소를 erase로 제거하고 새로 들어오는 오른쪽 요소를 insert로 추가합니다.

전체 시간 복잡도는 요소 하나당 O(log K)의 삽입·삭제·조회가 수행되므로 O(N log K)입니다. 매 윈도우마다 최댓값을 선형 탐색하는 O(N×K) 방식보다 효율적이며, 특히 K가 클수록 그 성능 차이가 두드러집니다.