[프로그래머스 lv3] 스타 수열 풀이

해설

스타 수열을 만들기 위한 조건은 다음과 같다.

> 스타 수열의 원소들을 2개씩 나누었을 때 각 집합이 포함하는 공통된 원소가 있을 것 < 

따라서, a에 등장하는 각 원소를 공통 원소로 하는 최대 스타 수열을 찾고 이 중에서도 가장 긴 수열의 길이를 리턴하면 된다.

 

1) a에는 0부터 a.size() 미만의 원소가 포함되어있다. a를 순회하면서 각 원소들의 등장 횟수를 cnt 배열에 저장하자.

 

2) a에 등장한 각 수 i를 순회하면서 i를 공통 원소로 하는 최대 스타 수열의 길이를 구해보자.

- 이때, cnt[i]가 0이라면 i를 공통 원소로 하는 스타 수열을 만들 수 없다.

- cnt[i]가 현재까지의 최대 스타 수열 길이 ans보다 작거나 같다면, i를 공통 원소로 하는 최대 스타 수열을 만들어도 그 길이가 ans보다 커질 수 없다. 따라서, 위 두 경우에는 최대 스타 수열의 길이를 별도로 구하지 않고 pass 한다.

- a를 순회하면서 j번째 원소를 확인한다. 만약 (a[j] = i && a[j+1] != i) 이거나 (a[j] != i && a[j+1] = i) 이면 공통 원소와 공통 원소가 아닌 수를 묶은 한 세트를 스타 수열에 추가할 수 있다. 스타 수열에 추가할 수 있는 세트 수를 구한 뒤 ans과 비교하여 최댓값을 갱신한다.

 

3) ans는 2개씩의 원소 쌍 개수를 의미하므로 ans*2를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int n;
vector<int> cnt(500005, 0);

int solution(std::vector<int> a) {

    n = (int)a.size();
    for (int i=0; i<n; i++) cnt[a[i]]++;

    int ans = 0;
    for (int i=0; i<n; i++) {
        if (!cnt[i]) continue;
        if (cnt[i] <= ans) continue;

        int res = 0;
        for (int j=0; j<n-1; j++) {
            if (a[j] == i && a[j+1] != i) {
                res++;
                j++;
            }
            else if (a[j] != i && a[j+1] == i) {
                res++;
                j++;
            }
        }
        ans = max(res, ans);
    }

    return ans*2;
}