René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"p.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)","articleBody":"제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.\r\n\r\np.g. 596의 '이중 우선순위 큐' 풀이1, 3 (이중 구조 방식)에 질문이 있어 문의 드립니다.\r\n\r\n풀이1, 3 모두 언어의 차이(java, kotlin)만 있을 뿐, 모두 이중 구조 방식으로 풀이하고 있습니다.\r\n하지만 값을 추출한 후, 대응하는 다른 힙의 엘리먼트를 삭제하는 과정이 비효율적이라고 생각합니다.\r\n=\u003e 최대값 추출의 경우, 최대힙에서 최대값을 추출 후, 해당 값을 최소힙에서 remove() 메서드를 통해 제거\r\n=\u003e 최소값 추출의 경우, 최소힙에서 최소값을 추출 후, 해당 값을 최댜힙에서 remove() 메서드를 통해 제거\r\n\r\n우선순위 큐의 이점은 최대값과 최소값 추출을 O(log n)에 수행하여 완전탐색 O(n)에 비해 빠르다는 것이지만,\r\n이후, remove() 메서드를 사용하면 결국 시간복잡도 O(n)의 연산으로 우선순위 큐를 사용하는 의미가 사라집니다.\r\n\r\n전체 엘리먼트 관리를 아래와 같이 전체 엘리먼트 개수로 하게 되면, 값 추출의 시간복잡도가 O(log n)이 됩니다.\r\n```\r\nimport java.util.*\r\n\r\nclass Solution {\r\n    fun solution(operations: Array\u003cString\u003e): IntArray {\r\n        // 우선순위 큐 선언, 자바 기본은 최소 힙이므로 최대 힙으로 정렬 지정\r\n        val minHeap: Queue\u003cInt\u003e = PriorityQueue()\r\n        val maxHeap: Queue\u003cInt\u003e = PriorityQueue(Collections.reverseOrder())\r\n        var totalCnt = 0\r\n        // 명령어 목록을 하나씩 순회하면서 해당하는 작업 수행\r\n        operations\r\n            .map { it.split(\" \") }\r\n            .forEach { op -\u003e\r\n                // 삽입 연산\r\n                when (op[0]) {\r\n                    \"I\" -\u003e { // 추출 연산\r\n                        minHeap.add(op[1].toInt())\r\n                        maxHeap.add(op[1].toInt())\r\n                        totalCnt++\r\n                    }\r\n\r\n                    \"D\" -\u003e { // 삭제 연산\r\n                        if (totalCnt \u003e 0) {\r\n                            when (op[1]) {\r\n                                // 값이 1인 경우 최댓값 추출\r\n                                \"1\" -\u003e maxHeap.poll()\r\n                                // 값이 -1인 경우 최솟값 추출\r\n                                \"-1\" -\u003e minHeap.poll()\r\n                            }\r\n                            if (--totalCnt == 0) {\r\n                                maxHeap.clear()\r\n                                minHeap.clear()\r\n                            }\r\n                        }\r\n                    }\r\n                }\r\n            }\r\n\r\n        // 최종결과인 최댓값과 최솟값을 추출하고 값이 없다면 0, 아니라면 해당 값으로 리턴\r\n        return intArrayOf(\r\n            maxHeap.poll() ?: 0,\r\n            minHeap.poll() ?: 0\r\n        )\r\n    }\r\n}\r\n```\r\n\r\n검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.","author":{"url":"https://github.com/hoogom88","@type":"Person","name":"hoogom88"},"datePublished":"2024-02-16T06:21:34.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/4/java-algorithm-interview/issues/4"}