[프로그래머스] 스타 수열 (JAVA)

문제 설명

다음과 같은 것들을 정의합니다.

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

제한사항

a의 길이는 1 이상 500,000 이하입니다.
a의 모든 수는 0 이상 (a의 길이) 미만입니다.

Code

1트

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int ret = 0;
		Map<Integer, List<Integer>> hm = new HashMap<>();
        // 숫자별 index 저장
        for(int i=0; i<a.length ; i++) {
        	int n = a[i];
        	if(!hm.containsKey(n)) hm.put(n, new ArrayList<>());
        	hm.get(n).add(i);
        }
        for(Map.Entry<Integer, List<Integer>> e : hm.entrySet()) {
        	int s=0, len=0;
        	for(int idx : e.getValue()) {
                if(idx<s) continue;
        		while(s<a.length && a[s]==e.getKey()) {
        			s++;
        		}
        		if(s<a.length) len+=2;
        		if(s<idx) s = idx;
        		s++;
        	}
        	ret = Math.max(ret, len);
        }
        return ret;
    }
}

2트 (다른사람 풀이 참고)

class Solution {
    public int solution(int[] a) {
        int[] count = new int[a.length];
        for(int num : a) count[num]++;
        
        int ret = 0;
        
        for(int i=0 ; i<a.length ; i++) {
        	if(count[i]==0) continue;
        	if(count[i]<=ret) continue;
        	int len = 0;
        	for(int j=0 ; j<a.length-1 ; j++) {
        		if(a[j]!=i && a[j+1]!=i) continue;
        		if(a[j]==a[j+1]) continue;
        		len++;
        		j++;
        	}
        	ret = Math.max(ret, len);
        }
        
        return ret*2;
    }
}

Comment

1트때는 숫자별 index를 저장하여 flexible index로 윈도우 진행했었다. (통과)
2트때 다른사람 풀이를 봤는데, 그럴필요 없이 생각의 전환을 하여 진행하였다. 보면 단순하게 현재 값과 다음값을 비교하여 진행하면 간단하게 되는것이다. 역시... 오늘도 배웁니다.