C++에서 최대 고유 요소를 가지는 부분 수열의 개수 구하기

문제 소개

정수만으로 이루어진 배열 arr[]가 주어졌을 때, 고유한(중복되지 않는) 요소를 최대한 많이 포함하는 부분 수열의 개수를 구하는 것이 이 문제의 목표입니다.

예를 들어 배열이 [4, 1, 2, 3, 4]라면, 고유 요소를 최대로 포함하는 부분 수열은 [4, 1, 2, 3]과 [1, 2, 3, 4], 두 가지입니다.

예제로 이해하기

입력 − arr[] = { 1, 3, 5, 4, 2, 3, 1 }

출력 − 최대 고유 요소를 가지는 부분 수열의 개수: 4

설명 − 고유한 요소는 1, 2, 3, 4, 5로 총 5개입니다. 해당하는 부분 수열은 다음과 같습니다.

[ 1, 3, 5, 4, 2 ], [ 3, 5, 4, 2, 1 ], [ 5, 4, 2, 3, 1 ], [ 1, 5, 4, 2, 3 ]

입력 − arr[] = { 5, 4, 2, 1, 3 }

출력 − 최대 고유 요소를 가지는 부분 수열의 개수: 1

설명 − 모든 요소가 서로 다르므로 가능한 부분 수열은 배열 하나뿐입니다.

접근 방식

이 문제의 핵심 아이디어는 다음과 같습니다. 모든 요소가 고유하다면 부분 수열의 개수는 1(배열 자신)이지만, 어떤 값이 k번 중복되어 나타난다면 그 값은 서로 다른 k개의 부분 수열에 각각 포함될 수 있습니다. 따라서 unordered_map을 사용해 각 고유 요소의 빈도를 계산한 뒤, 모든 빈도를 곱하면 원하는 답을 얻을 수 있습니다.

정수 배열 arr[]를 입력으로 받습니다.
Max_distinct_subseq(int arr[], int size) 함수는 배열과 그 크기를 받아 최대 고유 요소를 가지는 부분 수열의 개수를 반환합니다.
count를 1로 초기화합니다. 모든 요소가 고유하다면 배열 자체가 유일한 부분 수열이기 때문입니다.
unordered_map<int, int> hash;를 선언해 모든 고유 요소의 빈도를 저장합니다.
for 루프로 배열을 순회하며 hash[arr[i]]++로 각 요소의 빈도를 갱신합니다.
이어서 for 루프로 해시를 순회하며 각 빈도(it->second)를 기존 count에 곱합니다. 같은 값이 x번 등장하면 x개의 서로 다른 부분 수열에 속할 수 있기 때문입니다.
최종적으로 count에는 모든 빈도의 곱이 저장되며, 이를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
    int count = 1;
    unordered_map<int, int> hash;
    for (int i = 0; i < size; i++){
        hash[arr[i]]++;
    }
    for (auto it = hash.begin(); it != hash.end(); it++){
        count = count * (it->second);
    }
    return count;
}
int main(){
    int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of subsequences having maximum distinct elements are: 3

결과 분석

배열 { 3, 7, 3, 3, 1, 5, 6, 9 }에서 고유한 요소는 1, 3, 5, 6, 7, 9로 총 6개입니다. 이 중 값 3이 세 번 등장하고 나머지 요소는 한 번씩만 나타나므로, 부분 수열의 개수는 3 × 1 × 1 × 1 × 1 × 1 = 3이 됩니다.

복잡도 분석

시간 복잡도: O(n) — 배열을 한 번 순회해 빈도를 계산한 뒤, 고유 요소 수만큼 다시 순회합니다.
공간 복잡도: O(n) — 고유 요소의 빈도를 저장하기 위한 해시 맵이 필요합니다.

참고로 배열이 매우 길고 중복이 많은 경우 빈도들의 곱이 int 범위를 초과할 수 있으므로, 필요하다면 long long 타입을 사용하는 것이 안전합니다.