프로그래머스: 명예의 전당 (1)

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int k = 3;

        int[] score = {10, 100, 20, 150, 1, 100, 200};

        Solution sol = new Solution();

        int[] result = sol.solution(k, score);

        System.out.println(Arrays.toString(result));
    }

    public int[] solution(int k, int[] score) {

        int[] answer = new int[score.length];

        Integer[] stageOfhonor = new Integer[score.length];
        Arrays.fill(stageOfhonor, -1);
        for (int x=0; x<score.length; x++) {
            // 점수 하나를 명예의 전당에 추가
            stageOfhonor[x] = score[x];
            // 내림차순 정렬
            Arrays.sort(stageOfhonor, Collections.reverseOrder());
            // k가 그 이상이라면 k-1번째 인덱스의 값을 담자.
            if (x < k) {
                answer[x] = stageOfhonor[x];
            } else {
                answer[x] = stageOfhonor[k-1];
            }
        }
        return answer;
    }
}

 

다른 분들은 우선순위 큐(priorityQueue)를 사용했다.

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int k = 3;

        int[] score = {10, 100, 20, 150, 1, 100, 200};

        Solution sol = new Solution();

        int[] result = sol.solution(k, score);

        System.out.println(Arrays.toString(result));
    }

    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for(int i = 0; i < score.length; i++) {
            /*
             * score 배열의 i번째 요소를 우선순위 큐에 추가합니다. 
             * 이 때, 우선순위 큐는 자동으로 요소를 정렬합니다.
             */
            priorityQueue.add(score[i]);

            /*
             * 우선순위 큐의 크기가 k보다 크면, 
             * 가장 작은 요소(우선순위가 가장 높은 요소)를 큐에서 제거합니다. 
             * 이렇게 하면 우선순위 큐에는 항상 k개의 요소만 유지됩니다.
             */
            if (priorityQueue.size() > k) {
                priorityQueue.poll(); //가장 작은 요소 제거
            }

            answer[i] = priorityQueue.peek();
        }
        return answer;
    }
}

 

 

우선순위 큐가 뭔지 잘 몰라서 아름다워 보인다.

우선순위 큐(PriorityQueue)는 특정 조건에 따라 우선순위를 결정하고, 그 우선순위가 가장 높은 요소부터 제거되는 자료구조다. 자바의 PriorityQueue 클래스는 기본적으로 최소 힙(Min Heap)을 구현하므로, 가장 작은 요소가 가장 먼저 제거된다.

이 코드에서 PriorityQueue는 다음과 같이 동작한다:

1. priorityQueue.add(score[i]): score 배열의 i번째 요소를 우선순위 큐에 추가합니다. 이 때, 우선순위 큐는 자동으로 요소를 정렬한다.
2. if (priorityQueue.size() > k) { priorityQueue.poll(); }: 우선순위 큐의 크기가 k보다 크면, 가장 작은 요소(우선순위가 가장 높은 요소)를 큐에서 제거합니다. 이렇게 하면 우선순위 큐에는 항상 k개의 요소만 유지된다.
3. answer[i] = priorityQueue.peek();: 우선순위 큐의 맨 위에 있는 요소(가장 작은 요소)를 answer 배열의 i번째 요소로 설정한다. peek() 메소드는 큐의 맨 위 요소를 반환하지만, 큐에서 제거하지는 않는다.