코딩 테스트

Lv1. 명예의 전당 - 우선 순위 큐(선입 선출)

pjm1n 2025. 10. 28. 21:25

문제

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

풀이

import java.util.*
class Solution {
    fun solution(k: Int, score: IntArray): IntArray {
        val answer = IntArray(score.size)
        
        // 하루 당 명예의 전당에 등록될 점수리스트
        val minArray = PriorityQueue<Int>()
        
        score.forEachIndexed { index, i ->
            minArray.offer(i)
            if(index >= k) {
                minArray.poll()
            }
            answer[index] = minArray.first()
            
        }
        return answer
    }
}

IntArray(요소의 개수)

하루의 점수 최소값을 저장하여 매일 발표된 명예의 전당 점수들을 반환하기 위해 선언해준다.

IntArray(score.size)는 해당 개수만큼 0으로 초기화된 intArray를 반환한다. array는 원소의 값을 바꿀 수 있지만 배열의 크기를 바꿀수는 없다.

PriorityQueue(오름차순 큐)

import java.util.*을 통해 임포트를 반드시 해주어야한다.

PriorityQueue는 우선순위 큐이다. 들어간 순서대로 꺼내는 것이 아닌 “값의 우선 순위”에 따라 꺼내는 순서가 결정되는 큐이다.

기본 값은 오름차순 구조이다.

val pq = PriorityQueue<Int>()
pq.offer(5)
pq.offer(2)
pq.offer(10)

다음과 같이 값을 넣었다고 가정하면 내부적으로는 항상 [2,5,10]으로 정렬된 상태가 유지된다.

  • offer(): 리스트의 add()와 같은 기능이다.
  • poll(): PriorityQueue는 기본적으로 최소 힙 구조이다. 즉, 가장 작은 값이 우선순위가 높으므로 가장 작은 값부터 제거한다.
  • peek(): 요소를 제거하지 않고 현재 가장 작은 값만 확인가능하다.

PriorityQueue<Int>(compareByDescending { it })

하지만 내림 차순 큐인 경우는 값의 우선순위가 가장 큰 값이므로 내림차순으로 정렬되며, poll()을 통한 제거 또한 가장 큰 값부터 제거된다.