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

문제 링크

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

코딩테스트 연습 - 스타 수열

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 배열 속 숫자들의 개수를 카운트 (HashMap 사용), 이를 우선순위 큐를 통해 내림차순으로 정렬 (숫자, 숫자 개수)
2. 우선순위 큐에서 개수가 많은 숫자대로 꺼내 배열을 순서대로 탐색하면 해당 숫자가 걸린 위치에서 탐색
   1. 위치가 처음이라면 뒤에 숫자가 동일하지 않다면 수열에 포함
   2. 위치가 마지막이라면 그 앞의 숫자가 동일하지 않고 수열에 포함이 안되어 있다면 수열에 포함
   3. 위치가 중간이라면 앞 뒤 숫자들에 대해 조건 탐색 후 수열에 포함 (앞 숫자를 먼저 탐색)
3. 위의 조건대로 수열에 쌍이 추가될수록 +2를 추가하고, 최종 수열 길이와 답을 비교해 더 큰 값을 저장
4. 우선순위 큐에서 숫자를 꺼내 탐색을 반복하다 숫자 개수*2 가 답보다 작다면 탐색 종료

 이 문제 속 스타 수열의 경우 조건이 매우 복잡해, 단순한 완전 탐색으로 일일히 조건에 맞는 수열을 찾기에는 매우 복잡해진다. 그래서 문제의 조건 속 하나는 무조건 만족하게 한 상태로 탐색을 시작해야 문제 해결이 쉬워지는데, 이 경우 수열 속 각 쌍에 동일한 숫자가 존재해야 함을 우선 해결하는 것이 좋다.

 우선 주어진 a 배열을 돌며 숫자들의 개수를 센다(필자는 HashMap 사용). 이후 해당 숫자와 숫자의 개수를 하나의 클래스로 만든 다음 우선순위 큐에 모두 넣어, 숫자 개수의 내림차순으로 정렬되도록 전 처리를 진행한다. 이후엔 우선 순위 큐에서 숫자와 숫자 개수를 뽑아 탐색을 진행한다. 이 탐색의 목적은 a 배열을 순차대로 돌며 뽑은 숫자가 나왔을 때, 해당 숫자의 앞과 뒤 중 스타 수열의 쌍이 될 수 있는 지를 비교한 다음 가능하다면 수열에 추가해주는 것이다. 만약 해당 숫자 위치가 a 배열 시작이라면 무조건 뒤의 숫자를 추가하고, 숫자 위치가 배열 끝이라면 그 앞의 숫자와 함께 수열의 쌍이 될 수 있는 지, 중간이라면 숫자의 앞과 뒤가 수열의 쌍이 될 수 있는 지를 체크하고 포함된다면 수열의 길이 +2, 아니라면 다음 탐색을 반복하면 된다.

 이렇게 하나의 수에 대해 스타 수열 길이를 계산하고 답과 비교해 더 큰 값을 저장하면 되며, 만약 다음 탐색에서 숫자의 개수가 n개인데 답이 2*n보다 크다면, 이는 해당 숫자의 탐색을 진행해봤자 구할 수 있는 스타 수열 최대 길이가 답보다 작기 때문에 탐색을 중지해버리면 된다.

 

class Solution {
    public int solution(int[] a) {
        int answer = 2;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        PriorityQueue<Infor> pq = new PriorityQueue<>();

        if (a.length < 2) {
            return 0;
        } else if (a.length == 2) {
            return 2;
        }

        for (int i = 0; i < a.length; i++) {//숫자들의 개수 카운트
            if (hashMap.containsKey(a[i])) {
                hashMap.replace(a[i], hashMap.get(a[i]) + 1);
            } else {
                hashMap.put(a[i], 1);
            }
        }

        for (Map.Entry<Integer, Integer> elem : hashMap.entrySet()) {//우선순위 큐를 통해 내림차순
            pq.add(new Infor(elem.getKey(), elem.getValue()));
        }

        while (!pq.isEmpty()) {//개수가 많은 숫자 순서대로
            int result = 0, lastIndex = -1;
            Infor infor = pq.poll();

            if (answer >= infor.count * 2) {//최대 길이가 답을 못 넘는 경우
                break;
            }

            for (int i = 0; i < a.length; i++) {
                if (a[i] == infor.num) {//해당 숫자인 상태
                    if (i == 0) {//수열의 처음인 경우
                        if (a[i] != a[i + 1]) {
                            lastIndex = 1;
                            result += 2;
                        }
                    } else if (i == a.length - 1) {//수열의 마지막인 경우
                        if (lastIndex < i - 1 && a[i] != a[i - 1]) {//앞이 부분 수열에 포함 x
                            lastIndex = i;
                            result += 2;
                        }
                    } else {//수열의 중간인 경우
                        if (lastIndex < i - 1) {
                            if (a[i] != a[i - 1]) {//i 이전 인덱스 숫자를 부분 수열에 포함할 수 있는 경우
                                lastIndex = i;
                                result += 2;
                            } else if (a[i] != a[i + 1]) {//i 다음 인덱스 숫자를 부분 수열에 포함할 수 있는 경우
                                lastIndex = i + 1;
                                result += 2;
                            }
                        } else if (lastIndex == i - 1 && a[i] != a[i + 1]) {//i 다음 인덱스 숫자를 부분 수열에 포함할 수 있는 경우
                            lastIndex = i + 1;
                            result += 2;
                        }
                    }
                }
            }

            answer = Math.max(answer, result); //최대값을 답으로 최신화
        }

        return answer;
    }

    class Infor implements Comparable<Infor>{//우선순위 큐 삽입용 클래스
        int num, count;

        public Infor(int num, int count) {
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(Infor o) {
            if (this.count > o.count) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}

결과