[프로그래머스] level 3 - 스타 수열 (C++)

문제 설명

• 어떤 수열 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 해주세요.

 

 

문제 풀이

처음엔 각 숫자마다 개수를 세서 가장 많은 숫자의 개수에 곱하기 2를 하려고 했는데, 같은 숫자가 여러번 중복되어 나타나면 스타수열을 이룰 수 없으니 모든 숫자마다 이룰 수 있는 숫자 쌍의 개수를 계산하기로 했다.

 

단순히 앞뒤 숫자가 나와 다르다면 카운트를 할 수도 없는게, 1011 같은 형태라면 앞에 10은 짝을 이룰 수 있지만 세번째 숫자인 1은 이미 첫번째 1이 0과 짝을 이루었고 뒤의 1은 같은 숫자라 짝을 이루지 못하기 때문에 최종적으로 나올 수 있는 짝은 1개 뿐인 것이다. 이를 고려해서 이전 숫자와 짝을 이루는 숫자를 기억하고 비교하여 짝이 중복되는 경우는 피할 수 있었지만, 반대로 짝을 이룰 수 있는 경우까지 카운트를 안해버리는 경우가 나타나기도 했다.

 

0121 에서 앞의 01이 서로 짝을 이루었어도 0과 2는 다른숫자 이므로 12 또한 짝을 이룰 수 있으니 2의 짝은 1로 저장된다. 이 상태에서 다음 1로 넘어가게 되면 2의 짝은 1로 저장되어 있으므로 두번째 1은 2와 짝을 이룰 수 없다고 판정되는 것이다. 이를 피하기 위해 이전 숫자의 짝이 되는 숫자의 짝 인덱스 또한 저장하기로 하였다. 코드가 더러워지는 느낌이지만 어쩔 수 없었다...  다행이도 여기서 더 추가되는 인덱스 없이 문제를 해결할 수 있었다. 다음에는 좀 더 깔끔한 구조를 짤 수 있도록 구상해야겠다.

 

#include <string>
#include <vector>

using namespace std;
int solution(std::vector<int> a) {
    int answer = 0;
    
    // 짝을 이룰 수 있는 개수
    vector<vector<int>> pair_count(a.size(), vector<int>(1, 0));

    int before = a[0]; // 이전 숫자
    int before_pair = -1; // 이전 숫자와 짝을 이루는 숫자의 인덱스
    int before_before_pair = -1; // 이전숫자와 짝을 이루는 숫자의 짝 인덱스

    for (int i = 1; i < a.size(); i++)
    {
        if (a[i] == before) before_pair = -1;

        else if (a[i] != before)
        {
            // 이전 숫자가 짝을 이루지 않고 있으면 각각 짝 개수 증가
            if (before_pair == -1)
            {
                pair_count[before][0] += 1;
                pair_count[a[i]][0] += 1;
                before_before_pair = i;
                before_pair = i - 1;
            }
            // 이전 숫자의 짝이 현재 숫자와 다른 숫자이거나
            // 같은 숫자더라도 그 짝이 이전숫자가 아니라면 현재 숫자가 짝을 이룰 수 있음
            else if (a[before_pair] != a[i] || before_before_pair != i - 1) {
                pair_count[a[i]][0] += 1;
                before_before_pair = before_pair;
                before_pair = i - 1;
            }
            // 현재 숫자가 짝을 이루지 못했음
            else {
                before_pair = -1;
            }
            before = a[i];
        }
    }

    int count = 0;
    for (int i = 0; i < a.size(); i++) count = max(pair_count[i][0], count);
    if (count < 2) answer = 0;
    else answer = count * 2;

    return answer;
}