[Kotlin] 프로그래머스 > 코딩테스트 연습 > 힙(Heap) > 이중우선순위큐

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한 사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

 

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

 

풀이

처음에는 당연히 PriorityQueue를 사용하는 문제인 줄 알고 어떻게 해서든 이걸 써서 만점을 받아보겠다고 고군분투했다. 하지만 PriorityQueue에서 값을 하나 삭제하고 다시 넣을 땐 잘 정렬된 상태로 add 되지 않았고, 점점 코드는 복잡해져 갔다. 코드는 점점 복잡해져만 갔고…….

class SolutionKt {

    fun solution(operations: Array<String>): IntArray {
        val q = PriorityQueue<Int>()
        operations.forEach { operation ->
            operation.split(" ").let {
                val op = it[0]
                val num = it[1].toInt()
                when(op) {
                    "I" -> q.insert(num)
                    "D" -> q.delete(num)
                    else -> {} // do nothing
                }
                println("$operation :: $q")
            }
        }
        return if (q.size == 0) {
            arrayOf(0, 0).toIntArray()
        } else if (q.size == 1) {
            arrayOf(q.peek(), q.peek()).toIntArray()
        } else {
            arrayOf(q.elementAt(q.size-1), q.peek()).toIntArray()
        }
    }

    fun PriorityQueue<Int>.insert(num:Int) {
//        this.add(num)
        val tmp = this.toIntArray()
        this.clear()
        tmp.forEachIndexed { index, any -> this.add(any) }
        this.add(num)
    }

    fun PriorityQueue<Int>.delete(num:Int) {
        if(this.isEmpty()) return
        if (num == -1) { // delete min
//            this.poll()
            val tmp = this.toIntArray()
            this.clear()
            tmp.forEachIndexed { index, any -> if(index!=0) this.add(any) }
        } else if (num == 1) { // delete max
//            this.remove(this.elementAt(this.size-1))
            val tmp = this.toIntArray()
            this.clear()
            tmp.forEachIndexed { index, any -> if(index!=tmp.size-1) this.add(any) }
        } else {
            // do nothing
        }
    }

}

이런 코드가 되었는데, 이거보다는 그냥 배열로 min, max 쳐서 구하는 게 훨씬 간결하고 정확했다. 

(PriorityQueue로 하려 했던 코드는 테스트케이스 하나를 통과하지 못했었음)

 

아래 코드가 간단하게 배열로 구현한 정답 코드이다. 괜히 복잡하게 생각하다가 더 헤맨 케이스;;

class SolutionKt {

    fun solution(operations: Array<String>): IntArray {
        val arr = arrayListOf<Int>()
        operations.map { it.split(" ") }
            .map { it[0] to it[1].toInt() }
            .forEach { operation ->
                when (operation.first) {
                    "I" -> arr.add(operation.second)
                    "D" -> {
                        if (arr.isEmpty()) return@forEach
                        val v = if (operation.second == 1) arr.maxOrNull() else arr.minOrNull()
                        v.let { arr.remove(v!!) }

                    }
                    else -> {
                    } // do nothing
                }
            }
        return if (arr.size == 0) {
            intArrayOf(0, 0)
        } else {
            intArrayOf(arr.maxOrNull()!!, arr.minOrNull()!!)
        }
    }

}

 

---

https://programmers.co.kr/learn/challenges