C++에서 크기가 K인 모든 부분 배열의 최대 고유 요소 찾기

문제 설명

이 문제에서는 정수 배열과 정수 K가 주어집니다. 우리의 과제는 중복되지 않은(고유한) 요소만을 대상으로, 크기가 K인 모든 부분 배열에서 최대 고유 요소를 찾아 출력하는 프로그램을 작성하는 것입니다.

예제를 통해 문제를 살펴보겠습니다.

입력 −

array = {4, 1, 1, 3, 3}
k = 3

출력 −

4 3 1

설명 −

크기가 3인 부분 배열
{4, 1, 1} → 고유 요소 중 최댓값 = 4
{1, 1, 3} → 고유 요소 중 최댓값 = 3
{1, 3, 3} → 고유 요소 중 최댓값 = 1

해결 접근 방법

가장 단순한 방법은 두 개의 반복문을 사용해 모든 부분 배열을 직접 만들고, 각 부분 배열에서 고유한 요소를 찾은 뒤 그중 최댓값을 출력하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(N×K)로 비효율적입니다.

더 효율적인 해결책은 슬라이딩 윈도우(sliding window) 기법을 해시 테이블과 자가 균형 이진 탐색 트리(self-balancing BST)와 함께 활용하는 것입니다.

구체적으로는 배열을 순회하면서 길이 K 구간에 포함된 요소들의 등장 횟수를 해시 테이블(map)에 저장하고, 한 번만 등장한 고유 요소들은 set에 보관합니다. 그 후 set의 최댓값을 출력하고, 윈도우가 한 칸씩 이동할 때마다 동일한 과정을 반복합니다. 만약 현재 구간에 고유 요소가 하나도 존재하지 않는다면 -1을 출력합니다.

이 방식의 시간 복잡도는 O(N log K)로, 단순히 매번 부분 배열을 새로 검사하는 방식보다 훨씬 빠른 성능을 보입니다.

예제

다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
void maxUniqueSubArrayElement(int A[], int N, int K){
    map<int, int> eleCount;
    for (int i = 0; i < K - 1; i++)
       eleCount[A[i]]++;
    set<int> uniqueMax;
    for (auto x : eleCount)
       if (x.second == 1)
          uniqueMax.insert(x.first);
    for (int i = K - 1; i < N; i++) {
       eleCount[A[i]]++;
       if (eleCount[A[i]] == 1)
          uniqueMax.insert(A[i]);
       else
          uniqueMax.erase(A[i]);
       if (uniqueMax.size() == 0)
          cout<<"-1\t";
       else
          cout<<*uniqueMax.rbegin()<<"\t";
       int x = A[i - K + 1];
       eleCount[x]--;
       if (eleCount[x] == 1)
          uniqueMax.insert(x);
       if (eleCount[x] == 0)
          uniqueMax.erase(x);
   }
}
int main(){
    int a[] = { 4, 3, 2, 2, 3, 5};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
    cout<<"The maximum unique element for a subarray of size "<<k<<" is\n";
    maxUniqueSubArrayElement(a, n, k);
    return 0;
}

출력

The maximum unique element for a subarray of size 4 is
4 -1 5

코드 동작 원리 정리

위 코드는 세 단계로 동작합니다. 첫째, 초기 윈도우(K-1개 요소)의 등장 횟수를 map에 기록하고 고유 요소를 set에 넣습니다. 둘째, 윈도우의 오른쪽 끝에 새 요소를 추가하면서 등장 횟수가 1이 되면 set에 삽입하고, 2 이상이 되면 set에서 제거합니다. 셋째, 윈도우의 왼쪽 끝 요소를 제거하면서 등장 횟수 변화에 따라 set을 갱신합니다. 이 과정을 통해 매 윈도우마다 set의 최댓값(rbegin)을 상수 시간(log K 삽입/삭제 포함)에 얻을 수 있습니다.