[프로그래머스 / 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의 길이) 미만입니다.

시도

1. 비트 마스킹을 이용한 DFS 완전 탐색

문제를 풀기 전 다양한 알고리즘을 나열해 두고, 그 중 가장 정답에 가까울 것 같은 알고리즘을 선택하였는데 그것이 DFS 완전탐색이었다. 다만, 미처 조건을 깊게 고려하지 못하였다. 주어진 배열의 길이는 500,000 으로 각 배열의 원소 사용 여부에 따라 재귀함수를 이용해 DFS를 구현한다면 바로 StackOverflow가 발생한다.

2. DP를 사용한 풀이

다음으로는 DP의 사용 가능성을 확인해 보았다.

가령, n번째 원소까지만 주어졌을 때의 최대 스타 수열 길이를 알고 있다면 n+1번째 원소가 추가되었을 때의 최대 스타 수열의 길이를 알 방법이 있는지 확인해 보았다. 그러나, 앞에서부터 n번째 까지의 입력에 대한 최대 스타 수열 길이는 정답에 밀접한 관련이 없었다.

정답 설명

결국, 혼자서 해결하지 못하고 다른 사람들의 풀이를 참고해 힌트를 얻었다.

문제 풀이의 핵심은 다음과 같다.

1. 스타 수열을 구하는 데 핵심이 되는 것은 교집합의 선택이다.
2. 주어진 배열에서의 숫자의 최댓값은 배열의 길이이다.

문제를 해결하는 기본적인 아이디어는 다음으로 요약할 수 있다.

• 특정 수 k를 스타 수열에서의 교집합으로 설정한다.
• 앞에서부터 배열을 탐색하며 다음의 과정을 진행한다.
  • j번째 원소가 k라인 경우
    • 교집합으로 설정할 k를 발견하였음을 플래그 변수로 저장 후 탐색을 계속 진행한다.
  • j번째 원소가 k가 아닌 경우
    • 만약 이전에 k를 발견하였음이 플래그 변수에 저장되어 있다면 해당 k값과 j번째 원소를 하나의 집합으로 설정한다. (이번 탐색에서의 집합 개수를 1 증가시키고, 플래그 변수를 초기화 한다.)
    • 이전에 k를 발견하지 못했을 경우, j+1번째 변수를 확인한다.
      • j+1번째 변수가 k인 경우 j번째와 j+1번째 수를 하나의 집합으로 설정한다.
      • j+1번째 변수가 k가 아닐 경우 탐색을 계속 진행한다.

이를 통해 최대 O(n^2)의 시간 안에 문제를 해결할 수 있다.

하지만, 이 방법만으로는 시간이 부족하였고, 추가적인 최적화를 진행하여 문제를 해결하였다.

소스 코드

import java.util.*;
class Solution {
    public int solution(int[] a) {
        
        int[] numbers = new int[a.length];
        LinkedList<Intersection> list = new LinkedList<Intersection>();
        int maxLen = 0;
        for(int i = 0; i<a.length; i++){
            numbers[a[i]]++;
        }
        for(int i = 0; i<a.length; i++){
            if(numbers[i] != 0)
                list.add(new Intersection(i, numbers[i]));
        }
        
        Collections.sort(list);
        
        for(int i = 0; i<list.size(); i++){
            Intersection now = list.get(i);
            if(maxLen > now.count){
                return maxLen * 2;
            }
            int len = 0;
            int remain = -1;
            for(int j = 0; j<a.length; j++){
                if(len >= now.count ){
                    return now.count * 2;
                }
                if(a[j] == now.number){
                    remain = j;
                    continue;
                }
                if(remain != -1){
                    len++;
                    remain = -1;
                    continue;
                }
                if(j+1 < a.length && a[j+1] == now.number){
                    len++;
                    j++;
                    remain = -1;
                }
            }
            if(maxLen < len)
                maxLen = len;
        }    
        return maxLen * 2;
    }
    
}
class Intersection implements Comparable<Intersection>{
    int count;
    int number;
    
    public Intersection(int number, int count){
        this.number = number;
        this.count = count;
    }
    
    public int compareTo(Intersection i){
        return i.count - this.count;
    }
}