https://school.programmers.co.kr/learn/courses/30/lessons/138477
문제요약
"명예의 전당"이라는 프로그램에서 매일 1명의 가수가 노래를 부르고, 점수를 부여한다.
상위 k번 째 가수의 점수까지 명예의 전당에 기록되고, 매일 명예의 전당의 최하위 점수를 발표한다.
명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 함수를 만들어 보자.
제한사항
- 3 ≤ k ≤ 100
- 7 ≤ score의 길이 ≤ 1,000
- 0 ≤ score[i] ≤ 2,000
입출력 예
| k | score | result |
|---|---|---|
| 3 | [10, 100, 20, 150, 1, 100, 200] | [10, 10, 10, 20, 20, 100, 100] |
| 4 | [0, 300, 40, 300, 20, 70, 150, 50, 500, 1000] | [0, 0, 0, 0, 20, 40, 70, 70, 150, 300] |
문제풀이
매일 명예의 전당의 크기를 k로 고정시키면서, 그 중 최소값을 매일 기록한 리스트를 뽑으면 되는 문제이다.
동적 리스트의 최소값 (혹은 최대값)을 얻는 방법에는 대표적으로 Priority Queue와 Heap이 있겠지만, 나 같은 경우에는 Priority Queue가 좀 더 친숙해서 이 방법을 사용하였다. 모든 score의 원소를 돌면서, 명예의전당 (즉 pq)의 크기가 k가 될 때 까지 채운다음, 그 이후에는 원소값과 pq의 최소값을 비교하는 방식이다.
코드
Java
import java.util.*;
class Solution {
public int[] solution(int k, int[] score) {
List<Integer> answer = new ArrayList<>();
Queue<Integer> fame = new PriorityQueue<>();
for (int s : score) {
fame.add(s);
if (fame.size() > k) {
fame.poll();
}
answer.add(fame.peek());
}
return answer.stream()
.mapToInt(i -> i)
.toArray();
}
}Python
from queue import PriorityQueue
def solution(k, score):
answer = []
pq = PriorityQueue()
for s in score:
if pq.qsize() < k:
pq.put(s)
else:
if s > pq.queue[0]:
pq.get()
pq.put(s)
answer.append(pq.queue[0])
return answer