[프로그래머스][C++] 스타 수열

스타 수열

문제 링크

스타 수열

분석

수열 a가 주어질 때, 스타 수열이 될 수 있는 가장 긴 부분 수열의 길이를 구하여 반환해야합니다.

수열 a가 스타 수열이 되기위한 조건은 다음과 같습니다.

• 수열의 길이는 짝수여야 한다.
• 인접한 쌍을 (a[0], a[1]), (a[2], a[3]), ...로 나누었을 때, 각 쌍에는 두 원소가 서로 달라야 한다.
• 각 쌍에는 특정 수 x가 반드시 포함되어 있어야 한다.

예를 들어 [1,2,1,3,4,1,1,3]은 스타 수열입니다.
{1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

풀이

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int solution(std::vector<int> a) {
    int answer = 0;
    
    unordered_map<int, int> countMap;
    
    // 각 수의 등장 횟수 세기
    for (int number : a)
    {
        ++countMap[number];
    }
    
    // 기준 숫자를 하나씩 잡고 시도
    for (auto [x, count] : countMap)
    {
        // 현재 기준 숫자로 만들 수 있는 쌍이 현재 최대 길이보다 작다면 스킵
        if (count * 2 <= answer)
        {
            continue;
        }
        
        // 현재 기준 숫자로 만들 수 있는 쌍 카운트
        int pairCount = 0;
        
        // 인접한 쌍을 검사
        for (int i = 0; i < a.size() -1; ++i)
        {
            // 현재 기준 숫자가 포함되어있지 않은 경우 스킵
            if (a[i] != x && a[i + 1] != x)
            {
                continue;
            }
            // 현재 기준 숫자와 다음 인덱스의 값이 같은 경우 스킵
            if (a[i] == a[i + 1])
            {
                continue;
            }
            
            // 유효한 쌍이므로, 카운트 증가
            ++pairCount;

            // 한칸 더 이동
            ++i;
        }
        
        // 최대 길이 갱신
        answer = max(answer, pairCount * 2);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 각 수의 등장 횟수를 세는 반복문 $O(n)$
• 기준 숫자를 정하고 순회하는 반복문 $O(n)$
• 각 기준에 대해 인접한 쌍을 탐색하는 반복문 $O(n)$
• $O(n) + O(n) \times O(n)$

공간 복잡도는 $O(n)$입니다.

• 모든 숫자의 등장 횟수를 저장하는 unordered_map<int, int> countMap $O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 3.69MB)
테스트 4 〉 통과 (0.01ms, 4.22MB)
테스트 5 〉 통과 (0.01ms, 4.22MB)
테스트 6 〉 통과 (0.01ms, 4.16MB)
테스트 7 〉 통과 (0.01ms, 4.12MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.02ms, 4.22MB)
테스트 11 〉 통과 (0.02ms, 4.19MB)
테스트 12 〉 통과 (0.01ms, 4.22MB)
테스트 13 〉 통과 (8.63ms, 13.8MB)
테스트 14 〉 통과 (9.78ms, 20.9MB)
테스트 15 〉 통과 (14.18ms, 21.1MB)
테스트 16 〉 통과 (19.41ms, 21.2MB)
테스트 17 〉 통과 (66.55ms, 22.9MB)
테스트 18 〉 통과 (15.96ms, 10.3MB)
테스트 19 〉 통과 (26.79ms, 17.6MB)
테스트 20 〉 통과 (82.62ms, 34.3MB)
테스트 21 〉 통과 (89.67ms, 34.4MB)
테스트 22 〉 통과 (102.56ms, 34.5MB)
테스트 23 〉 통과 (65.11ms, 26.6MB)
테스트 24 〉 통과 (122.30ms, 33.7MB)
테스트 25 〉 통과 (93.75ms, 34.4MB)
테스트 26 〉 통과 (99.19ms, 32.9MB)
테스트 27 〉 통과 (50.05ms, 23MB)
테스트 28 〉 통과 (0.01ms, 4.21MB)