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

https://programmers.co.kr/learn/courses/30/lessons/70130

코딩테스트 연습 - 스타 수열

 

 

[난이도] level3
[유형] Greedy

[풀이]
a배열의 최대 길이가 50만이기 때문에 한번 배열을 스캔하면서 최대 길이의 스타수열을 찾아야합니다.

"a의 모든 수는 0 이상 (a의 길이) 미만입니다."
위의 조건에 의해 나올 수 있는 수도 50만 미만이기 때문에 두개의 배열을 이용해 문제를 풀 수 있습니다.
cnt[500000],idx[500000] 두 배열을 선언하여

cnt[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 최대길이
idx[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 마지막 index

위와 같은 값을 저장하는 용도로 사용합니다.

이제 a배열을 0부터 순회하면서
i번째 원소를 확인중일 때, 조건을 만족한다면 cnt[a[i]], idx[a[i]]를 업데이트 할 수 있습니다.

i번째 원소의 왼쪽에 짝이 있는 경우와, 오른쪽에 짝이 있는 경우가 있을 수 있습니다.

왼쪽에 짝이 있으려면,
idx[a[i]] 즉, a[i]를 교집합으로 하는 스타 수열의 마지막 index보다는 i-1이 작아야하며 (idx[a[i]] < i-1)
a[i] != a[i-1]을 만족해야 합니다. (서로 값이 달라야 하기 때문에)

i-1만 검사해도 되는 이유는 만약 a[i] == a[i-1] 이고 a[i-1] != a[i-2] 라면 (예를 들어 a[i]가 1일때 [...2,1,1] 이런 형태)
idx[a[i]]가 i-1일 것이므로 idx[a[i]] < i-1 에서부터 조건을 만족하지 못하여 a[i] != a[i-1]는 검사할 필요가 없어집니다.

왼쪽에 짝이 있다면 i가 이제 마지막 index가 되므로 idx[a[i]]=i로 업데이트 해주고
짝이 한개 추가되었기 때문에 cnt[a[i]]++를 해주고 다음 index를 검사합니다.

만약 왼쪽에 짝이 없다면 오른쪽에 있는지 검사해야 합니다.
오른쪽에 a[j] != a[i] 를 만족하는 j가 있다면 idx[a[i]]=j 로 업데이트 해주면 됩니다.

for문을 돌때마다
먼저 if(i<=idx[a[i]]) continue 를 추가해줍니다.
위 조건에 걸렸다는 것은 스타 수열의 index가 i 뒤에 있다는 것이기 때문에 i는 스타 수열에 포함될 수 없어 검사할 필요가 없습니다.

최종적으로 cnt[i] (0<=i<(a의 길이)) 중에 최댓값을 구하고, 쌍의 개수이므로 그 값에 2배를 해주면 됩니다.

알고리즘 분류가 애매하지만 매 루프마다 최적의 index를 고르는 것이기 때문에 Greedy 문제로 생각됩니다.

 

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int mxN=5e5;
int cnt[mxN],idx[mxN],ans;
int solution(std::vector<int> a) {
    memset(idx,-1,sizeof(idx));
    for(int i=0;i<a.size();i++){
        if(i<=idx[a[i]]) continue;
        if(i>0&& idx[a[i]] < i-1 && a[i]!=a[i-1]){
            cnt[a[i]]++, idx[a[i]]=i;
            continue;
        }
        int j=i;
        while(++j<a.size() && a[j] == a[i]);
        if(j<a.size()) cnt[a[i]]++, idx[a[i]]=j;
    }
    for(int i=0;i<a.size();i++) ans=std::max(ans,cnt[i]);
    return ans*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스타_수열.cpp