p.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)

[hoogom88]

제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.

p.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)에 질문이 있어 문의 드립니다.

풀이1, 3 모두 언어의 차이(java, kotlin)만 있을 뿐, 모두 이중 구조 방식으로 풀이하고 있습니다.
하지만 값을 추출한 후, 대응하는 다른 힙의 엘리먼트를 삭제하는 과정이 비효율적이라고 생각합니다.
=> 최대값 추출의 경우, 최대힙에서 최대값을 추출 후, 해당 값을 최소힙에서 remove() 메서드를 통해 제거
=> 최소값 추출의 경우, 최소힙에서 최소값을 추출 후, 해당 값을 최댜힙에서 remove() 메서드를 통해 제거

우선순위 큐의 이점은 최대값과 최소값 추출을 O(log n)에 수행하여 완전탐색 O(n)에 비해 빠르다는 것이지만,
이후, remove() 메서드를 사용하면 결국 시간복잡도 O(n)의 연산으로 우선순위 큐를 사용하는 의미가 사라집니다.

전체 엘리먼트 관리를 아래와 같이 전체 엘리먼트 개수로 하게 되면, 값 추출의 시간복잡도가 O(log n)이 됩니다.

import java.util.*

class Solution {
    fun solution(operations: Array<String>): IntArray {
        // 우선순위 큐 선언, 자바 기본은 최소 힙이므로 최대 힙으로 정렬 지정
        val minHeap: Queue<Int> = PriorityQueue()
        val maxHeap: Queue<Int> = PriorityQueue(Collections.reverseOrder())
        var totalCnt = 0
        // 명령어 목록을 하나씩 순회하면서 해당하는 작업 수행
        operations
            .map { it.split(" ") }
            .forEach { op ->
                // 삽입 연산
                when (op[0]) {
                    "I" -> { // 추출 연산
                        minHeap.add(op[1].toInt())
                        maxHeap.add(op[1].toInt())
                        totalCnt++
                    }

                    "D" -> { // 삭제 연산
                        if (totalCnt > 0) {
                            when (op[1]) {
                                // 값이 1인 경우 최댓값 추출
                                "1" -> maxHeap.poll()
                                // 값이 -1인 경우 최솟값 추출
                                "-1" -> minHeap.poll()
                            }
                            if (--totalCnt == 0) {
                                maxHeap.clear()
                                minHeap.clear()
                            }
                        }
                    }
                }
            }

        // 최종결과인 최댓값과 최솟값을 추출하고 값이 없다면 0, 아니라면 해당 값으로 리턴
        return intArrayOf(
            maxHeap.poll() ?: 0,
            minHeap.poll() ?: 0
        )
    }
}

검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.