문제 푼 날짜 : 2021-05-19

문제

문제 링크 : 링크텍스트

접근 및 풀이

다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
1. x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
2. x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
3. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.

위에 제시된 스타 수열이 되기 위한 조건을 봤을 때, 직관적으로 2번의 조건을 통해 문제를 풀어나가야 한다고 생각했다.
교집합의 원소가 반드시 1개 이상 존재해야하고, 이 원소를 어떻게 설정하느냐에 따라서 최종 스타 수열의 길이가 달라질 것이기 때문에, 단순한 접근으로 주어진 수열에서 등장하는 숫자들의 빈도를 이용해서 스타 수열의 조건을 체크해주면 된다고 생각했다.

이를 구현하기 위해서 수열에 존재하는 숫자들의 개수를 세어주었고, 존재하는 숫자들을 교집합의 원소로 설정해가면서 스타 수열의 조건이 만족하는 경우를 체크하였다.
이 때, 가지치기 할 수 있는 케이스가 존재한다.
예를 들어 주어진 수열 [1,2,1,3,4,1,1,3] 에서 교집합 원소가 1일 경우, [1,2,1,3,4,1,1,3] 으로 길이 8인 스타 수열이 만들어 지는데, 교집합 원소가 3이라고 생각할 경우엔 아무리 잘 만들어도 최대 길이 4인 스타 수열밖에 만들어질 수가 없다. 따라서 이런 경우는 그냥 스타 수열 조건에 대해 체크하지 않고 넘어가도록 하였다.

코드

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

using namespace std;

int solution(std::vector<int> a) {
    int answer = -1;
    vector<int> counter(a.size() + 1, 0); // a에 있는 수를 저장하기 위해 초기화
    
    for (int i = 0; i < a.size(); i++) {
        counter[a[i]]++; // a에 있는 수들의 갯수 저장
    }
    
    for (int i = 0; i < counter.size(); i++) {
        if (!counter[i]) continue; // 수열에 존재하지 않는 숫자
        if (counter[i] <= answer) continue; // 체크안해봐도 되는 케이스
        
        int cnt = 0;
        
        for (int j = 0; j < a.size() - 1; ) {
            if ((a[j] == i || a[j + 1] == i) && (a[j] != a[j + 1])) { // 스타수열 조건을 만족하는 경우
                cnt++; // 스타수열 길이 계산
                j += 2;
            } else {
                j += 1;
            }
        }
        answer = max(answer, cnt);
    }
    
    return answer * 2; // 길이는 2배해서 return
}

결과

피드백

문제를 봤을 때 쉬워보여서 단순히 그리디하게 문제를 풀어나가려고 했다. 왜 이렇게 문제를 풀 때마다 처음 드는 생각은 전부 그리디인지...
하지만 생각보다 고려해줘야할 것이 많다는 것을 알게 되었고, 꼼꼼하고 깊이 생각해봐야하는 케이스가 있다는 것을 참조 사이트를 통해 알게 되었다. 정말 똑똑하신 분들이 많은 것 같다.
문제를 풀 때, 주어진 테스트 케이스에 대해서 좀 더 깊이 생각하고, 예외 케이스도 빠르게 빠르게 떠올릴 수 있도록 연습이 더 필요할 것 같다.

참조 사이트

링크텍스트