[프로그래머스] 힙 : 이중우선순위큐 Kotlin

I를 만나면 Queue에 넣어주고

D 1을 만나면 최댓값, D -1을 만나면 최솟값을 삭제하면 되는 간단한 문제이다.

 

흠,, 그러나 우리는 Queue에서 최댓값과 최솟값을 같이 컨트롤 하기가 까다롭고

 

그것을 해결하라는게 이 문제의 의도인거 같다.

 

힙 유형에 해당하는 만큼 Priority Queue를 사용해보고자 했고 Max Heap, Min Heap 2가지를 사용했다.

 

그래서 D 1일 때는 Max Heap쪽으로 옮기고, D -1일 때는 Min Heap으로 옮긴 후 Poll 해준다.

 

그러면 자동 정렬이 된다!

 

효율적인거 같지는 않지만,,, Queue는 한쪽으로 밖에 안되니까,,, Deque로 자동 정렬하며 할 수 있는 방법이 있을까..?

 

import java.util.*

class Solution {
    fun solution(operations: Array<String>): IntArray {
        var answer = intArrayOf(0,0)

        var queueMin = PriorityQueue<Int>()
        var queueMax = PriorityQueue<Int>(Comparator.reverseOrder())

        for(i in 0..operations.size-1){
            var data = operations[i].split(" ")
            if(data[0].equals("I")){
                queueMin.offer(data[1].toInt())
            }
            else{
                if(data[1].equals("1")){
                    for(j in 0..queueMin.size-1){
                        queueMax.offer(queueMin.poll())
                    }
                    queueMax.poll()
                }
                else{
                    for(j in 0..queueMax.size-1){
                        queueMin.offer(queueMax.poll())
                    }
                    queueMin.poll()
                }
            }
        }

        for(i in 0..queueMax.size-1){
            queueMin.offer(queueMax.poll())
        }
        if(!queueMin.isEmpty()) {
            answer[1] = queueMin.poll()
        }


        for(i in 0..queueMin.size-1){
            queueMax.offer(queueMin.poll())
        }
        if(!queueMax.isEmpty()) {
            answer[0] = queueMax.poll()
        }

        return answer
    }
}