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

📜 문제

문제 링크

💡 나의 풀이

   총 2가지 풀이 방법으로 문제를 풀어보았다.
  첫번째는 우선순위큐를 사용하지 않고 ArrayDeque를 오름차순으로 정렬해서 index가 0인 element를 최솟값, lastIndex에 있는 element를 최댓값으로 사용하는 방식으로 문제를 풀었다.
   두번째는 두가지 우선순위큐를 사용했다. minHeap과 maxHeap이 그 두개다. minHeap과 maxHeap이 가지고 있는 요소는 똑같지만 root에 최솟값이 있냐, 최댓값이 있냐 차이다.

   첫번째 풀이는 명령어로 "I"가 들어올 때마다 ArrayDeque를 정렬해줘야하기 때문에 최악의 경우 시간복잡도가 대략 O(N^2logN) (시그마 NlogN이라고 해야하나)인 것으로 예상된다. 통과한 게 신기할 정도!
  반면 두번째 풀이는 우선순위 큐의 삽입, 삭제 모두 O(logN)만에 일어나기 때문에 시간복잡도가 O(NlogN)이다.

⌨️ 코드1

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

        val queue = ArrayDeque<Int>()
        operations.forEach { operation ->
            val (command, number) = operation.split(" ")

            when (command) {
                "I" -> {
                    queue.add(number.toInt())
                    queue.sort()
                }
                "D" -> {
                    if (number.toInt() < 0) {
                        queue.removeFirstOrNull()
                    } else {
                        queue.removeLastOrNull()
                    }
                }
            }
        }

        if (queue.isNotEmpty()) {
            answer[0] = queue.removeLast()
            answer[1] = queue.removeFirst()
        }

        return answer
    }
}

⌨️ 코드2

import java.util.*

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

        val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
        val minHeap = PriorityQueue<Int>()

        operations.forEach { operation ->
            val (command, number) = operation.split(" ")

            when (command) {
                "I" -> {
                    maxHeap.offer(number.toInt())
                    minHeap.offer(number.toInt())
                }
                "D" -> {
                    if (number.toInt() > 0) {
                        maxHeap.poll()?.let { minHeap.remove(it) }
                    } else {
                        minHeap.poll()?.let { maxHeap.remove(it) }
                    }
                }
            }
        }
        
        if (maxHeap.isNotEmpty()) {
            answer[0] = maxHeap.peek()
            answer[1] = minHeap.peek()
        }

        return answer
    }
}

😄 느낀 점

괜히 제목에 있는 대로 풀기 싫어가지고 PriorityQueue는 안쓰고 ArrayDeque를 써서 오히려 시간복잡도가 엉망인 풀이를 만들어냈다😂 코드 치기 전이나, 전에 알아보기 힘들면 코드를 다 작성한 후라도 시간복잡도 제대로 따지고 갈 것!!!!!
그래도 그 덕에 java.util.ArrayDeque랑 kotlin.collections.ArrayDeque가 따로 있다는 사실도 알게된 귀한 시간이었다:)