[Programmers] Lv.0 | 명예의 전당 (1) | Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/138477

 

풀이

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        
        // 매일 발표되는 "명예의 전당 최하위 점수"를 담을 배열
        int[] answer = new int[score.length];
        
        // 우선순위 큐 (PriorityQueue)
        // - 가장 작은 값이 항상 맨 앞에 있게 유지됨 (min-heap)
        // - 즉, 명예의 전당에서 "꼴찌 점수"를 빠르게 알 수 있음
        PriorityQueue<Integer> hall = new PriorityQueue<>();
        
        // 매일 하루씩 처리
        for (int day = 0; day < score.length; day++) {
            
            int todayScore = score[day]; // 오늘 가수의 점수
            
            // 1) 아직 명예의 전당에 k명이 안 찼다면 그냥 추가
            if (hall.size() < k) {
                hall.offer(todayScore);
            } 
            // 2) 명예의 전당이 꽉 찼다면
            else {
                // - hall.peek() : 현재 명예의 전당 중 가장 낮은 점수(꼴찌)
                // 오늘 점수가 그보다 크면 명예의 전당에 들어갈 수 있음
                if (todayScore > hall.peek()) {
                    hall.poll();           // 기존 꼴찌 강퇴
                    hall.offer(todayScore); // 오늘 점수 입성
                }
                // 오늘 점수가 더 작으면 아무 일도 없음
                // 그냥 들어갈 가치가 없기 때문
            }
            
            // ★ 매일 발표되는 값: 명예의 전당 최하위 점수
            //   즉, 최소 힙의 맨 앞 요소(peek())
            answer[day] = hall.peek();
        }
        
        return answer;
    }
}