[Level 1] 명예의 전당 (1) - PriorityQueue

[내배캠 - 오늘의 문제]

문제의 point1. roof를 돌며 socre와 최소값과 비교하여 최소값을 밀어내고, socre를 배열에 넣어야 한다.

문제의 point2. roof를 돌 때마다, K개의 요소중 최소값을 뽑아내야 한다.

import java.util.PriorityQueue

class Solution {
    fun solution(k: Int, scores: IntArray): IntArray {
        val answer = IntArray(scores.size)
        val pq = PriorityQueue<Int>()

        for((index, score) in scores.withIndex()) {
            if(pq.size < k) {
                pq.add(score)
            }

            else if(score > pq.peek()) {
                pq.add(score)
                pq.poll()
            }

            answer[index] = pq.peek()
        }

        return answer
    }
}

 

 

 

- PriorityQueue를 사용한 이유

일반적으로 최소값을 뽑아야 할 때는 collection의 확장함수인 min()을 사용할 텐데

min()의 시간복잡도는 O(N)이지만, pq의 peek()는 항상 최소값을 반환하기 때문에 O(1)로 빠른 계산이 가능하다.

 

pq.peek() -> O(1), collection.min() -> O(N)

 

 

- 어떻게 peek() 값이 항상 최소값일까?

PriorityQueue는 내부적으로 이진트리의 형식을 갖추고 있기 때문에, 오름차순 혹은 내림차순으로 데이터를 저장하기 때문이다. 그래서 오름차순과 내림차순을 이용하여 최소값 또는 최대값을 O(1)로 뽑을 수 있다.

 

 

- 그렇다면 오름차순과 내림차순으로 PriorityQueue를 초기화하는 방법은?

// 오름차순
val pq = PriorityQueue<Int>() 

// 내림차순
val pq = PriorityQueue<Int>(Collections.reverseOrder())

 

 

- 요소를 추가했을 때, 오름차순 또는 내림차순으로 정렬이 되는지 자세히 코드를 들여다 보자

import java.util.*

fun main() {
    // 오름차순 pq
    val pq = PriorityQueue<Int>()
    // 내림차순 pq
    val pq2 = PriorityQueue<Int>(Collections.reverseOrder())

    // pq의 데이터 삽입 및 결과 출력 
    pq.addAll(listOf(1, 4, 3, 2, 5))

    println(pq)    // [1, 2, 3, 4, 5]
    println(pq.peek())    // 1

	// pq2의 데이터 삽입 및 결과 출력 
    pq2.addAll(listOf(1, 4, 3, 2, 5))

    println(pq2)    // [5, 4, 3, 1, 2]
    println(pq2.peek())    // 5

    // 삭제
    println("${pq.poll()}, $pq")      // 1, [2, 4, 3, 5]
    println("${pq2.poll()}, $pq2")    // 5, [4, 2, 3, 1]

    println(pq.size)    // 4

    // 최대값 순차적으로 뽑기
    while (pq2.isNotEmpty()) {
        println(pq2.poll())    // 4, 3, 2, 1
    }
}

pq를 출력한 결과는 [1, 2, 3, 4, 5]로 제대로 정렬된 모습을 보인다.

하지만, pq2를 출력했을 때는 예상했던 대로 [5, 4, 3, 2, 1]의 값이 아니다.

 

 

- 그 이유는 뭘까?

내부적으로는 최대 힙 구조(root의 값이 최대값)을 유지하고 있지만, 전체 배열이 완전히 내림차순으로 정렬된 상태를 유지하는 것은 아니다. (오름차순이라면, 부모 노드가 자식의 노드보다 작기만한 상태를 유지한다.)

 

따라서, 배열중 n번째의 최소값을 뽑기 위해서는 roof를 이용하여 n번 만큼 순차적으로 poll을 하면된다.

 

 

- 주의사항 : 내림차순으로 정렬하기 위해서는 아래 같이 스타 import를 해야한다. (Collections도 가져와야 하기 때문)

import java.util.PriorityQueue -> import java.util.*

 

 

- 궁금했던 점 : 요소의 삽입으로 add()와 offer() 메소드가 있던데 어떤 차이일까?

이전과 다르게 현재 Kotlin 버전(1.19.12)에서는 add를 호출하면 offer의 값을 리턴하도록 되어 있었다. (둘의 차이는 없다?)

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Collection#add})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
public boolean add(E e) {
    return offer(e);
}