[프로그래머스 Level 3] 스타 수열

문제

 

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

• 어떤 수열 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의 길이) 미만입니다.

 

 

---

풀이

 

해법을 알고나니 너무 허탈한 문제였다. 처음에 PowerSet(부분 집합)을 구하는 것으로 접근했다.

• 재귀를 이용한 부분 집합 → 시간 초과
• bit를 이용한 부분 집합 → 시간 초과
  
  

접근 방법을 바꿔 스타 수열이 가능한 후보를 먼저 탐색하고, 부분 집합을 구했더니 PASS 할 수 있었다.

• 스타 수열이 가능한 후보 : 주어진 배열 a에 있는 원소 개수의 집합
• 원소의 개수가 많을 수록 유력한 후보
  
  

스타 수열이 가능한 후보를 먼저 구하는 이유는 무엇일까?

 

원소의 개수가 많다는 것은 만들 수 있는 스타 수열의 길이가 길 가능성이 있다는 뜻이다.(물론, 개수가 많은 원소가 항상 정답은 아니다.) 즉, 개수가 많은 원소를 사용해서 스타 수열을 만들때 사용한 개수를 저장해두고 비교하면, 다음 원소에서 스타 수열을 구하지 않을 수 있다. 배열 [5, 2, 3, 3, 5, 3]으로 예를 들어보면,

 

1. 배열을 순회하면서 각 원소의 개수를 저장한다.
   • 원소 3은 3개, [3] = 3
   • 원소 5는 2개, [5] = 2
   • 원소 2는 1개, [2] = 1
   • 여기서 원소 3이 유력한 후보가 된다.
     
     
2. 원소 3으로 스타 수열을 만들어 보면 [2, 3, 3, 5], [2, 3, 5, 3]이 있고, 스타 수열의 길이는 4가 된다.
3. 원소 5로 스타 수열을 만들어 보면 [5, 2, 3, 5], [5, 2, 5, 3]이 있다. 역시 스타 수열의 길이는 4가 된다.
4. 원소 2로 스타 수열을 만들어 보면 [5, 2], [2, 3]이 된다. 스타 수열의 길이는 2가 된다.

원소 3은 총 3개의 원소가 있었다. 여기서 최대로 만들 수 있는 스타 수열의 길이는 6이고, 실제 스타 수열을 만들었을 때 길이는 4가 되었다. 즉, 우리는 스타 수열의 길이를 알아야하므로 원소 3의 스타 수열 길이가 2가 되지 않는 이상, 원소 5의 스타 수열은 구하지 않아도 된다. 원소 5는 최대로 만들 수 있는 스타 수열의 길이가 4이기 때문이다.

 

이후에는 문제에 나온 조건대로

• {x[0], x[1]}, {x[2], x[3]}, ... {x[2n-2], x[2n-1]} 의 교집합이 앞에서 선택한 후보가 되는지 확인
• 두 원소가 다른 숫자인지 확인
  
  

위 두 가지만 확인하면 스타 수열을 구할 수 있다.

 

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int solution(int[] a) {
        Map<Integer,Integer> map = new HashMap<>();
        int answer = -1;

        for(int n : a) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        for(int key : map.keySet()) {
            if(map.get(key) <= answer) continue;
            int count = 0;

            for(int i=0; i<a.length-1; i++) {
                if(a[i] != key && a[i+1] != key) continue;
                if(a[i] == a[i+1]) continue;
                count++;
                i++;
            }
            answer = Math.max(answer, count);
        }

        return answer * 2;
    }
}