[프로그래머스] 명예의 전당 - Java

이지연·2025년 12월 29일

코딩테스트 풀이(구현, 자료구조, 알고리즘)

목록 보기

13/50

프로그래머스 문제 URL

매일 점수가 들어올 때, “명예의 전당(상위 k개)”의 최하위 점수(= k등 점수)를 기록하는 문제
i번째 날까지의 점수 중 상위 k개만 유지하고, 그중 가장 낮은 점수를 answer[i]에 저장한다.

문제 접근

입력
k : 명예의 전당에 남길 인원 수(상위 k개)
score[] : 매일 새로 들어오는 점수(날짜 순)

예를 들어,
```
k = 3
score = [10, 100, 20, 150, 1, 100, 200]
```
매일 “상위 3개”를 갱신하면서, 그 안에서 가장 작은 값(=3등)을 answer에 기록한다.
출력
각 날짜 i에 대해 “그 시점의 명예의 전당 최하위 점수”를 담은 배열 answer를 반환한다.

제출

import java.util.*;

public class A02힙정렬문제풀이 {

    // 명예의 전당
    public static int[] solution138477(int k, int[] score) {
        int[] answer = new int[score.length];

        // 상위 k개를 유지하기 위한 최소힙
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < score.length; i++) {
            pq.add(score[i]);          // 오늘 점수 반영

            if (pq.size() > k) {       // k개 초과면
                pq.poll();             // 가장 작은 값 제거 -> 상위 k개만 남김
            }

            answer[i] = pq.peek();     // 상위 k개 중 최하위(=k등) 점수
        }
        return answer;
    }
}

핵심 개념

“상위 k개만 유지”가 핵심

모든 점수를 정렬해서 매번 k등을 찾으면 비효율적이다.
대신 상위 k개만 남기는 컨테이너를 유지하면 매일 정답을 바로 뽑을 수 있다.

왜 PriorityQueue(최소힙)를 쓰나?

PriorityQueue를 최소힙으로 두면, peek()가 “현재 들어있는 값 중 최소”를 즉시 가리킨다.
상위 k개를 유지할 때, “k개 중 가장 작은 값(=k등)”이 바로 필요하므로 최소힙이 딱 맞다.
매일 점수 하나를 넣고, k개 초과 시 최소값 하나를 빼는 방식으로 “상위 k개”만 유지된다.

루프 로직을 한 문장으로

pq에 오늘 점수를 넣고 → 크기가 k를 넘으면 최하위(최소값)를 제거하고 → 남은 것 중 최소값을 answer에 기록한다.

시간복잡도(왜 통과하는가)

매일 add 1번: 힙 연산이라 보통 log(현재 힙 크기)
매일 poll은 최대 1번(사이즈가 k 넘을 때만): 역시 log(k) 수준
그래서 전체는 대략 O(score.length * log k)로 동작한다.
k가 작거나 중간 정도면 매우 빠르게 처리된다.

출력 예시(직관 설명용)

입력

k = 3
score = [10, 100, 20, 150, 1, 100, 200]

흐름(요약):

1일차: → k등(최하위)=10
2일차: → 최하위=10[3]
3일차: → 최하위=10[3]
4일차: (10이 밀려남) → 최하위=20[4][3]
… 이런 식으로 “상위 3개”만 남기면서 최하위를 기록한다.

흔한 실수와 해결

❌ 실수	✅ 해결
PQ에 전부 넣고 한 번에 처리	“매일 정답 기록”이라 매일 갱신해야 함
최대힙을 써서 k등을 찾으려 함	k등은 “상위 k개 중 최솟값”이라 최소힙이 직관적
pq.size() 제한 없이 계속 add	`size > k`면 `poll()`로 k개 유지
`peek()` 타이밍이 헷갈림	“k개 유지한 후”의 `peek()`가 그날의 답