# [프로그래머스 138477] 명예의 전당 (1) - PriorityQueue와 삽질 기록
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/138477
문제 요약
매일 가수 한 명이 노래를 부르고 점수를 받는다. k일까지는 모든 점수가 "명예의 전당"에 오르고, 그 이후로는 새 점수가 기존 명예의 전당 목록의 최하위 점수보다 높을 때만 갈아치운다. 매일 명예의 전당의 최하위 점수를 배열로 반환해야 한다.
k = 3
score = [10, 100, 20, 150, 1, 100, 200]
result = [10, 10, 10, 20, 20, 100, 100]핵심은 "지금까지 뽑힌 점수들 중 최솟값"을 매일 빠르게 구해야 한다는 것.
1차 시도 - 배열 + 수동 스왑 (실패)
처음엔 이렇게 짰다.
int[] tempArr = new int[k];
tempArr[0] = score[0];
answer[0] = score[0];
for(int i=1; i<k; i++){
if(score[i]>tempArr[i-1]){
tempScore=tempArr[i-1];
tempArr[i-1]=score[i];
tempArr[i]=tempScore;
}
answer[i]=tempArr[i];
}문제점을 짚어보면:
for(i=1; i<k; i++)라서 k일 이후 데이터는 아예 처리가 안 됨score[i]를 바로 앞 슬롯 하나랑만 비교해서 스왑 → 제대로 된 정렬 삽입이 아님
-애초에answer[i]가 뭘 의미해야 하는지(그날까지 명예의 전당에 오른 점수들의 최솟값)를 명확히 안 하고 코드부터 짬
즉 "매일 최솟값을 빠르게 구하고, 필요하면 교체한다"는 알고리즘 설계 없이 바로 구현으로 들어간 게 문제였다.
필요한 자료구조 다시 생각하기
매일 해야 하는 연산을 정리하면:
- 명예의 전당이 아직
k개가 안 찼으면 → 그냥 추가 - 다 찼으면 → 현재 최솟값과 비교해서, 새 점수가 더 크면 최솟값을 빼고 새 점수를 넣음
- 그날의 답 = 현재 명예의 전당의 최솟값
즉 "최솟값을 빠르게 조회 + 빠르게 제거/삽입"이 계속 반복된다. 배열로 이걸 하려면 매번 최솟값을 찾는 스캔이 필요한데, Java에는 이걸 위해 만들어진 자료구조가 있다 — PriorityQueue (우선순위 큐).
PriorityQueue 관련해서 헷갈렸던 것들
offer()vsadd():Queue인터페이스 기준으로add()는 용량 제한으로 삽입 실패 시 예외를 던지고,offer()는false를 리턴한다. 근데PriorityQueue는 용량 제한이 없는 구조라 실질적으로 둘 다 동작이 같다 (관례상offer()를 씀).- "자동 정렬"이 아니다:
PriorityQueue는 전체를 정렬된 상태로 유지하지 않는다. 내부적으로 힙(heap) 구조라 "부모 노드 ≤ 자식 노드"라는 규칙만 지킨다. 그래서peek()/poll()은 항상 최솟값을 O(1)/O(log n)에 보장하지만, 순회(iterate)하면 오름차순이 아닐 수 있다. - 부모-자식 관계는 삽입 순서가 아니라 값 크기로 결정됨: 완전이진트리 구조상 "다음 빈자리"는 원소 개수(size)로 정해지지만, 넣고 나서 부모보다 작으면 계속 스왑(sift-up)하기 때문에 나중에 들어온 값이 먼저 들어온 값을 밀어내고 root(부모)가 될 수 있다.
- 채워지는 순서는 레벨 순회(BFS): 같은 레벨에서 왼쪽 → 오른쪽, 레벨은 위 → 아래로 채워진다. 이게 배열로 구현될 때
부모 index i의 자식이2i+1,2i+2가 되는 이유.
정답 1: PriorityQueue 풀이
import java.util.PriorityQueue;
class Solution {
public int[] solution(int k, int[] score) {
int[] answer = new int[score.length];
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 기본 min-heap
for (int i = 0; i < score.length; i++) {
if (pq.size() < k) {
pq.offer(score[i]);
} else if (pq.peek() < score[i]) {
pq.poll();
pq.offer(score[i]);
}
answer[i] = pq.peek();
}
return answer;
}
}pq.size() < k→ 아직 명예의 전당이 안 찼으면 그냥 추가- 다 찼는데 새 점수가 현재 최솟값(
peek())보다 크면 → 최솟값 빼고(poll()) 새 점수 추가(offer()) - 매일
pq.peek()이 그날의 답
시간복잡도 O(n log k)로, offer/poll이 각각 O(log k)라 충분히 효율적이다.
심화: PriorityQueue 없이 for문만으로 구현하기
힙을 안 쓰고 직접 배열로 같은 로직을 구현해보면서 겪은 삽질 과정.
설계
hall[k]: 현재 명예의 전당 점수들을 담는 배열count: 지금까지 채운 인원 수 (0부터 k까지)- 매일:
count < k면 빈자리에 채우고, 아니면hall안의 최솟값을 찾아서 새 점수와 비교 후 교체 - 그 후
hall[0 ~ count-1]범위에서 다시 최솟값을 찾아answer[i]에 저장
겪었던 버그들
1) 채우는 위치를 잘못 지정
hall[i]=score[i]; // ❌ i는 계속 커지는데 hall 크기는 k뿐→ hall[count]로 수정 (지금까지 채운 개수를 인덱스로 써야 함).
2) 최솟값 찾는 조건 부등호가 반대
if(minValue<hall[j]){ minIndex=j; ... } // ❌ 이건 최댓값을 찾는 조건→ if(minValue>hall[j])로 수정.
3) minIndex에 엉뚱한 변수를 대입
minIndex = i; // ❌ i는 바깥(날짜) 루프 변수
minIndex = count; // ❌ 이 시점에 count는 항상 k → 배열 범위 밖(out of bounds)→ 지금 훑고 있는 hall의 인덱스인 j를 대입해야 함.
4) 비교/교체 타이밍이 루프 도중
최솟값을 다 찾기도 전에 루프 안에서 score[i] > minValue를 판단하고 있었음. 최솟값 탐색이 끝난 뒤(루프 밖에서) 딱 한 번만 비교/교체해야 함.
5) return answer;가 for문 안에 있었음
for (...) {
...
return answer; // ❌ 첫 날(i=0) 처리하고 바로 함수 종료
}→ for문이 다 끝난 뒤로 이동.
6) answer[i]를 채우는 로직 자체가 없었음
hall을 채우거나 교체하는 로직만 있고, 정작 "그날의 최하위 점수"를 기록하는 부분이 빠져 있었음. if/else 양쪽 분기가 끝난 뒤 별도로 최솟값 스캔을 추가해야 했음.
7) 새로 추가한 min 스캔에서 minValue를 갱신 안 함
int minValue = hall[0];
for (int j=0; j<hall.length; j++) {
if (minValue > hall[j]) {
answer[i] = hall[j]; // ❌ minValue는 그대로, answer만 계속 덮어씀
}
}hall=[100, 10, 50]처럼 조건을 만족하는 값이 여러 개면 마지막으로 조건을 만족한 값(50)이 남아버려서 진짜 최솟값(10)이 아닌 값이 저장됨.
→ if 안에서 minValue = hall[j]도 같이 갱신해야 함.
8) 아직 안 채워진 슬롯(기본값 0)까지 포함해서 스캔
count < k인 초반 며칠은 hall의 뒷부분이 아직 비어있는(기본값 0) 상태인데, 스캔 범위를 hall.length(=k)로 고정해서 돌리면 이 0들이 "진짜 0점"처럼 취급돼서 최솟값이 틀어짐. 이 문제는 score 값 자체에 0점이 실제로 존재하는 테스트케이스([0, 300, 40, ...])가 있어서 더 헷갈렸음.
→ 스캔 범위를 hall.length가 아니라 count로 제한.
최종 for문 버전
class Solution {
public int[] solution(int k, int[] score) {
int[] answer = new int[score.length];
int[] hall = new int[k];
int count = 0;
for (int i = 0; i < score.length; i++) {
if (count < k) {
hall[count] = score[i];
count++;
} else {
int minValue = hall[0];
int minIndex = 0;
for (int j = 0; j < hall.length; j++) {
if (minValue > hall[j]) {
minIndex = j;
minValue = hall[j];
}
}
if (score[i] > minValue) {
hall[minIndex] = score[i];
}
}
int minValue = hall[0];
for (int j = 0; j < count; j++) {
if (minValue > hall[j]) {
minValue = hall[j];
}
}
answer[i] = minValue;
}
return answer;
}
}두 번 도는 min 스캔(교체 판단용 + answer 기록용)을 하나로 합칠 수도 있지만, 로직을 명확히 분리해두는 게 이해하기엔 더 편했다.
두 풀이 비교
| PriorityQueue | for문 직접 구현 | |
|---|---|---|
| 시간복잡도 | O(n log k) | O(n·k) |
| 코드 길이 | 짧음 | 김 (버그 낼 여지 많음) |
| 장점 | 최솟값 조회/교체를 라이브러리가 알아서 처리 | 힙 내부 동작 원리를 직접 체감 가능 |
k ≤ 100, score.length ≤ 1,000이라 이 문제에선 두 방식 다 성능 차이는 미미하지만, 데이터 크기가 커지면 PriorityQueue 쪽이 훨씬 유리하다.
배운 점
- 코드부터 짜지 말고, "매일 어떤 판단을 해야 하는가"를 먼저 자연어로 정리한 다음 구현했어야 했다.
- "최솟값을 빠르게 조회"하는 패턴이 필요하면 PriorityQueue(min-heap)를 먼저 떠올리기.
- 배열로 최솟값을 찾는 루프를 짤 때 자주 하는 실수 두 가지: (1) 기준값(
minValue)을 갱신하는 걸 깜빡함, (2) 스캔 범위를 "실제 채워진 만큼"이 아니라 배열 전체 길이로 잡아서 기본값(0)이 섞여 들어감. 이 두 개는 다른 문제 풀 때도 계속 조심해야 할 부분. - 배열 인덱스로 쓸 변수(
count,j,i)의 역할을 헷갈리면ArrayIndexOutOfBoundsException이나 조용한 논리 오류로 이어지니, 각 변수가 "무엇을 세는 값인지" 이름 붙일 때부터 명확히 하기.
