프로그래머스 명예의 전당 (1) JAVA 풀이 (우선순위 큐, PriorityQueue)

📌 문제 개요

매일 가수의 점수가 발표된다.

명예의 전당에는 항상 상위 k개의 점수만 유지하며, 매일 명예의 전당에 등록된 점수 중 가장 낮은 점수를 발표한다.

주어진 score 배열에 대해 매일 발표되는 최하위 점수를 구하는 문제이다.

---

📌 접근 방법

처음에는 모든 점수를 저장한 후 정렬을 반복하는 방법을 생각할 수 있다.

하지만 점수가 들어올 때마다 정렬을 수행하면 비효율적이다.

따라서 현재 명예의 전당에 포함된 점수들만 관리하는 PriorityQueue(최소 힙)를 사용한다.

---

📌 처리 순서

1. 오늘의 점수를 힙에 추가
2. 힙 크기가 k를 초과하면 최솟값 제거
3. 힙의 최솟값(peek)을 정답 배열에 저장

---

📌 핵심 아이디어

명예의 전당에는 항상 상위 k개의 점수만 존재해야 한다.

따라서 최소 힙의 크기를 k로 유지하면 된다.

예를 들어 k = 3일 때

10 추가
[10]

100 추가
[10, 100]

20 추가
[10, 20, 100]

150 추가
[10, 20, 100, 150]
↓
가장 작은 10 제거

[20, 100, 150]

결과적으로 힙에는 항상 상위 3개의 점수만 남는다.

그리고 힙의 최솟값이 곧 명예의 전당 최하위 점수이다.

---

📌전체 코드

import java.util.PriorityQueue;

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

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

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

        for (int i = 0; i < score.length; i++) {

            pq.offer(score[i]);

            if (pq.size() > k) {
                pq.poll();
            }

            answer[i] = pq.peek();
        }

        return answer;
    }
}

---

📄 정리

• PriorityQueue(최소 힙) 사용
• 힙에는 항상 상위 k개의 점수만 유지
• k개를 초과하면 가장 작은 점수 제거
• peek() 값이 매일 발표되는 명예의 전당 최하위 점수
• 상위 K개 유지 문제의 대표적인 PriorityQueue 활용 문제