코딩 테스트 - 스타 수열

스타 수열

문제 링크 : 스타 수열

문제 설명

다음과 같은 것들을 정의합니다.

• 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
  • 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.
• 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
  • x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
  • x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
  • x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
  • 예를 들어, [1,2,1,3,4,1,1,3]은 스타 수열입니다. {1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

1차원 정수 배열 a가 매개변수로 주어집니다. a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return 하도록 solution 함수를 완성해주세요. 이때, a의 모든 부분 수열 중에서 스타 수열이 없다면, 0을 return 해주세요.

제한 사항

• a의 길이는 1 이상 500,000 이하입니다.
  • a의 모든 수는 0 이상 (a의 길이) 미만입니다.

입출력 예

a	result
[0]	0
[5,2,3,3,5,3]	4
[0,3,3,0,7,2,0,2,2,0]	8

풀이 방법

• 스타 수열의 조건에서 교집합의 원소의 개수가 1 이상인 것으로 보아서, 빈도수가 가장 많은 숫자를 기준으로 우선 검사를 해서 스타 수열의 최고 길이를 판단하고자 했다.

1. 먼저, a를 순회하면서 숫자 별로 빈도수를 측정해서 빈도수가 많은 순서대로 정렬을 했다.
2. 빈도수가 많은 순서대로 그 숫자를 교집합으로 하는 가장 긴 스타 수열의 길이를 찾고자 했다.
3. 이미 저장되어 있는 스타 수열의 길이가 그 숫자의 빈도수보다 크거나 같은 경우에는 순회를 그만했다.
4. 스타 수열의 조건에 만족하기 위해서는 해당 숫자가 포함되면서, 그 전이나 다음 숫자와 동일하지 않아야 된다는 것을 통해서 최대 스타 수열의 길이를 구했다.

-> 해당 문제 풀이는 정렬할 때 O(NlogN)의 시간복잡도를 가지고, 가장 긴 스타 수열의 길이를 찾을 때 O(N*M)의 시간복잡도를 가질 것으로 보이고, N은 a의 수의 최대 값인 500,000, M은 a의 길이인 500,000으로 언뜻 보았을 때는 시간초과가 날 수도 있으나, 가지치기 때문에 시간초과는 안 날 것으로 보인다.

구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct numCount{
    int num;
    int count = 0;
};

int solution(std::vector<int> a) {
    // 숫자 별로 가장 많이 나온 순서대로 정렬하기
    unordered_map<int, int> frequency;
    for(int num : a){
        frequency[num]++;
    }
    
    vector<numCount> numCounts;
    for(auto it = frequency.begin(); it != frequency.end(); ++it){
        numCounts.push_back({it->first, it->second});
    }
    
    sort(numCounts.begin(), numCounts.end(), [](numCount a, numCount b){
        return a.count > b.count;
    });
    
    // 가장 많이 나온 숫자부터 그 숫자를 교집합으로 하는 가장 긴 스타 수열의 길이 찾기
    int answer = 0;
    
    for(int i = 0; i < numCounts.size(); ++i){
        int num = numCounts[i].num;
        int count = numCounts[i].count;
        
        if(answer >= count * 2) break;
        
        int maxCount = 0;
        
        for(int idx = 0; idx < a.size() - 1; ++idx){
            if((a[idx] == num || a[idx + 1] == num) && (a[idx] != a[idx + 1])){
                maxCount += 2;
                idx++;
            }
        }
        
        answer = max(answer, maxCount);
    }
    
    return answer;
}