[프로그래머스 Level.3] 스타 수열 (월간 코드 챌린지 시즌1 ) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 스타 수열

 

 

 

문제 설명

 

 

 

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

 

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

 

---

 

입출력 예

a	result
[0]	0
[5,2,3,3,5,3]	4
[0,3,3,0,7,2,0,2,2,0]	8

 

---

입출력 예 설명

 

 

입출력 예 #1

 

• a의 부분 수열 중에서 주어진 조건을 모두 만족하는 스타 수열이 없으므로, 0을 return 해야 합니다.

 

 

입출력 예 #2

 

• [5,2,5,3], [5,3,3,5] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 4를 return 해야 합니다.

 

 

입출력 예 #3

 

• [0,3,3,0,7,0,2,0] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 8을 return 해야 합니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        
        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] == 0) continue; // 원소 개수가 없으면 건너뜀
            if(cnt[i] <= answer) continue; // 원소 개수가 이미 다른 교집합 원소가 사용된 수 * 2 이하이면 건너뜀
            // (교집합 원소 사용된 횟수 * 2 가 최대 길이이기 때문에 answer보다 크게 나올 수 없음)
            
            int count = 0; // 해당 교집합 원소가 사용된 횟수
            
            for(int j=0; j<a.length-1; j++) {
                if(a[j] != i && a[j+1] != i) continue; // 교집합 원소의 개수는 1 이상
                if(a[j] == a[j+1]) continue; // 바로 다음 수와 동일하면 안된다. (x[0] != x[1], x[2] != x[3])
                count++;
                j++; 
            }
            
            if(count > 1) answer = Math.max(answer, count); // 1번만 사용되면 스타수열 길이가 2로 교집합을 갖는 두 집합이 안생김
        }
        
        return answer * 2; // 사용된 횟수마다 (j, j+1) 두 개씩의 원소를 가짐
    }
}

 

풀이

1. 교집합으로 삼을 원소를 구하기 위해 cnt 배열을 만들어  a 배열을 순회하며 각 원소의 개수를 해당 수에 해당하는 인덱스에 저장한다.
2. 이제 cnt 배열을 순회하며 해당 원소의 개수를 확인한 뒤 교집합으로 삼아 스타수열을 만든다.
3. 우선 해당 원소를 교집합으로 삼을 것이기 때문에 개수가 1개 이하라면 넘어간다.
4. 또한, 해당 원소의 개수 * 2가 answer 이하라면 해당 원소를 모두 사용하여 스타수열을 만들어도 길이가 answer와 같거나 작다는 것이므로 넘어간다.
5. 둘 다 아니라면 해당 원소로 스타수열의 길이를 구하도록 한다.
6. 스타수열을 만들면서 해당 원소가 사용된 횟수를 구하기 위해 int형 변수 count를 0으로 초기화한다.
7. 이제 a배열을 다시 순회하면서 문제에 주어진 조건대로 교집합 원소는 무조건 포함해야 하는 것과 한 집합에 속하는 두 수가 같으면 안되는 것을 확인하여 둘 다 아니라면 교집합으로 삼을 원소를 증가시키고 a[j]와 a[j+1] 두 수를 스타수열에 포함하였으니 j를 2증가시켜 다음 수를 확인하도록 한다. 조건에 걸린다면 j를 1만 증가시켜 다음 수를 확인하면 된다.
8. 이렇게 교집합 원소가 사용된 횟수를 구하여 사용된 횟수가 2 이상이라면 교집합 원소와 다른 수(j와 j+1)가 쌍을 이루므로 *2를 하여 answer와 비교하여 더 크다면 answer에 저장한다. (교집합 원소가 한 번만 사용되었다면 해당 원소를 교집합으로 각각 갖는 집합 두 개를 만들 수가 없다)