[138477] 명예의 전당 (1)

✔ 명예의 전당 (1)

[프로그래머스 138477]

문제 분석하기

최솟값 우선순위 큐를 이용해 문제에 접근

예) [1, 100, 20, 150, 1, 100, 200]

일차	1	2	3	4	5	6	7
score	1	100	20	150	1	100	200
명예의 전당 큐 (k = 3)	10 (최솟값)	10 (최솟값) 100	10 (최솟값) 100 20	10 (최솟값) 100 20 150 ↓ 20 (최솟값) 100 150	20 (최솟값) 100 150	20 (최솟값) 100 150 100 ↓ 100 (최솟값) 100 150	100 (최솟값) 100 150 200 ↓ 100 (최솟값) 150 200
발표 점수	10	10	10	20	20	100	100

손으로 풀어보기

1. 최솟값 우선순위 큐에 점수를 저장
   • 이때 점수의 갯수가 k개를 넘어간다면 큐의 최솟값을 삭제
2. 큐의 최솟값을 최하위 점수 배열에 저장
3. 최하위 점수 배열 반환

슈도코드 작성하기

k(명예의 전당 목록의 점수의 개수)
score(1일부터 마지막 날까지 출연한 가수들의 점수)
answer(매일 발표된 명예의 전당의 최하위 점수들)
queue(명예의 전당의 점수를 저장하는 최솟값 우선순위 큐)
for(i -> score의 길이만큼) {
    queue에 score[i] 집어넣기
    if(큐의 크기가 k보다 크다면) {
        가장 낮은 점수(최솟값)를 삭제
    }
    answer[i] = queue의 가장 낮은 점수(최솟값)를 저장
}
answer 반환

코드 구현하기

/**
 * 138477) 명예의_전당_(1)
 */
public class L065_138477 {
    // k(명예의 전당 목록의 점수의 개수)
    // score(1일부터 마지막 날까지 출연한 가수들의 점수)
    public int[] solution(int k, int[] score) {
        // answer(매일 발표된 명예의 전당의 최하위 점수들)
        int[] answer = new int[score.length];
        // queue(명예의 전당의 점수를 저장하는 최솟값 우선순위 큐)
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < score.length; i++) {
            // queue에 score[i] 집어넣기
            queue.add(score[i]);
            // 큐의 크기가 k보다 크다면
            if (queue.size() > k) {
                // 가장 낮은 점수(최솟값)를 삭제
                queue.poll();
            }
            // answer[i] = queue의 가장 낮은 점수(최솟값)를 저장
            answer[i] = queue.peek();
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L065_138477 solution = new L065_138477();

        int k = 4;
        int[] score = { 0, 300, 40, 300, 20, 70, 150, 50, 500, 1000 };

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

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