C++에서 주어진 크기의 부분 배열에 포함된 고유 정수의 최대 개수 구하기

문제 소개

이 문제에서는 크기가 n인 배열과 숫자 M이 주어집니다. 우리가 작성해야 할 프로그램은 주어진 크기의 부분 배열(sub-array) 안에 있는 고유한 정수의 최대 개수를 찾는 것입니다.

다시 말해, 중복을 제외한 서로 다른 원소를 가장 많이 포함하고 있는 크기 M짜리 부분 배열을 찾아야 합니다.

예제를 통해 문제를 자세히 이해해 보겠습니다.

입력 − array = {4, 1, 2, 1, 4, 3}, M = 4

출력 − 4

설명 −

크기가 4인 모든 부분 배열의 조합:
{4, 1, 2, 1} → 고유 원소 3개
{1, 2, 1, 4} → 고유 원소 3개
{2, 1, 4, 3} → 고유 원소 4개

단순한 접근 방식과 그 한계

가장 직관적인 방법은 크기 M인 모든 부분 배열을 생성한 뒤, 각 부분 배열에 포함된 고유 원소의 개수를 세는 것입니다. 그리고 그 값이 지금까지의 전역 최댓값보다 크면 더 큰 값을 저장하면 됩니다. 하지만 이 방법은 가능한 모든 경우를 일일이 검사해야 하므로 연산량이 많아 비효율적입니다.

효율적인 해결 방법: 슬라이딩 윈도우 기법

더 나은 해결책은 슬라이딩 윈도우(sliding window) 기법을 활용하는 것입니다. 크기 M의 윈도우를 만들고, 현재 윈도우에 포함된 고유 원소들을 해시 테이블에 저장해 관리하는 방식입니다.

윈도우는 다음과 같은 방식으로 만들고 이동시킵니다.

• 크기 M의 윈도우를 생성하고, 윈도우 안의 원소들을 해시 맵에 저장합니다.
• 이후 윈도우를 한 칸씩 이동시키면서 (M+1)번째 위치의 새 원소를 추가하고, 이전 윈도우에서 빠지는 원소는 제거합니다.

예제를 통해 풀이 과정을 살펴보며 솔루션을 더 깊이 이해해 보겠습니다 −

Array = {4, 1, 2, 1, 4, 3}

윈도우 크기, M = 4

위 표는 윈도우와 해시 맵이 어떻게 구성되는지, 그리고 고유 원소의 개수가 어떻게 계산되는지 보여 줍니다.

예제 코드

주어진 크기의 부분 배열에서 고유 정수의 최대 개수를 찾는 C++ 프로그램 −

#include<bits/stdc++.h>
using namespace std;
int maxUniqueElement(int a[],int N,int M){
    map<int,int> hashMap;
    int uniqueCountWindow=0;
    int uniqueCount=0;
    for(int i=0;i<M;i++) {
        if(hashMap.find(a[i])==hashMap.end()) {
            hashMap.insert(make_pair(a[i],1));
            uniqueCountWindow++;
        }
        else
            hashMap[a[i]]++;
    }
    uniqueCount = uniqueCountWindow;
    for(int i=M;i<N;i++) {
        if(hashMap[a[i-M]]==1) {
            hashMap.erase(a[i-M]);
            uniqueCountWindow--;
        }
        else
            hashMap[a[i-M]]--;
        if(hashMap.find(a[i])==hashMap.end()){
            hashMap.insert(make_pair(a[i],1));
            uniqueCountWindow++;
        }
        else
            hashMap[a[i]]++;
        uniqueCount=max(uniqueCount,uniqueCountWindow);
    }
    return uniqueCount;
}
int main(){
    int arr[] = {4, 1 ,2, 1, 4, 3};
    int M=4;
    int N=sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum number of unique elements in sub-array of size "<<M<<" is "<<maxUniqueElement(arr,N,M)<<endl;
}

출력

The maximum number of unique elements in sub-array of size 4 is 4

시간 복잡도 분석

모든 부분 배열을 검사하는 단순한 방식은 대략 O(N × M)의 시간이 걸립니다. 반면 슬라이딩 윈도우 기법은 각 원소를 정확히 한 번씩만 추가하고 제거하므로, std::map을 사용할 경우 O(N log M), unordered_map을 사용하면 평균 O(N)에 문제를 해결할 수 있습니다. 덕분에 배열의 크기가 커져도 훨씬 빠르게 동작합니다.