[pro] 프로그래머스 level3 70130 스타 수열 (Java)

[문제]

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

프로그래머스

 

[풀이]

먼저 수열에 나오는 숫자의 빈도수를 카운트 해준다. 

스타 수열이 충족해야 하는 조건 3가지 중, 가장 길이가 긴 스타 수열을 반환하는데 영향을 미치는 조건은 교집합의 원소의 개수가 1 이상이라는 조건이다.

0~n-1 까지의 숫자 x에 대해서 수열의 index를 이동시켜가며 index, index+1 의 숫자가 다르고, 숫자 x가 교집합으로 등장하는지를 확인해준다. 모든 조건을 만족하면 스타수열의 부분 수열이 될 수 있으므로 ans를 증가시켜준다. 여기서 ans는 해당 x(교집합 원소)가 스타수열에 등장하는 횟수가 될 것이다. (answer = Math.max(answer, ans)로 최댓값으로 갱신해줌)

따라서 cnt[x]가 현재의 answer와 같다면, x를 교집합 원소로 하는 스타수열의 최대값 역시 answer일 것이므로 구할 필요가 없다. 당연히 answer보다 작은 경우 역시 구할 필요 없다. 

 

우리는 answer를 x가 스타수열에 등장하는 횟수로 세었기 때문에 실제 스타수열의 길이는 answer*2가 된다.

 

[코드]

 

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        //a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return
        int[] cnt = new int[a.length];
        for(int i=0; i<a.length; i++){
            cnt[a[i]]++;
        }
        
        for(int i=0; i<cnt.length; i++){
            if(cnt[i] <= answer) continue; //이미 등장한 숫자보다 더 빈도가 적거나 같은 경우
            
            int ans = 0;
            for(int j=0; j<a.length-1; j++){
                if(a[j]!=a[j+1] && (i==a[j] || i==a[j+1])){
                    ans++;
                    j++;
                }
            }
            
            answer = Math.max(answer, ans);
        }
        
        return answer*2;
    }
}