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

코드 힌트

1. 값을 담을 자료구조 선택하기:
   • 이중 우선순위 큐는 최댓값과 최솟값을 효율적으로 삽입 및 삭제할 수 있는 자료구조를 사용해야 합니다.
   • PriorityQueue는 힙(Heap) 구조를 사용하여 요소를 정렬하고, 최소값을 빠르게 찾을 수 있습니다.
   • 최댓값을 빠르게 찾기 위해 Collections.reverseOrder()를 사용하여 내림차순 정렬된 PriorityQueue를 추가로 사용합니다.
   • 다른 자료 구조도 사용이 가능합니다
2. 명령어 처리:
   • 명령어가 I (삽입) 인 경우, 주어진 값을 두 개의 PriorityQueue에 추가합니다.
   • 명령어가 D (삭제) 인 경우, 다음을 처리합니다:
     • D 1: 최댓값을 삭제합니다.
     • D -1: 최솟값을 삭제합니다.
   • PriorityQueue에서 요소를 제거할 때, 각 큐에서 해당 요소를 동기화하여 제거해야 합니다.
3. 결과 반환:
   • 모든 연산이 종료된 후, 큐가 비어있으면 [0, 0]을 반환합니다.
   • 큐가 비어있지 않으면 [최댓값, 최솟값]을 반환합니다.

 

 

 

문제를 풀고난 후 다른 분들의 풀이를 보니 PriorityQueue에 remove를 하면 비효율적이다 라는 말이 있어서 찾아봤습니다

PriorityQueue에서 요소 제거의 비효율성

1. 힙 구조:
   • PriorityQueue는 힙(보통 최소 힙)으로 구현되어 있습니다. 힙은 부모 노드가 항상 자식 노드보다 작거나 같은 완전 이진 트리입니다.
   • 요소를 추가하거나 제거할 때 힙 속성을 유지하기 위해 O(log n)의 시간이 걸립니다.
2. 검색의 비효율성:
   • PriorityQueue는 힙 구조로 인해 요소의 순서가 정렬된 형태가 아니므로 특정 요소를 찾기 위해 전체 배열을 순회해야 합니다. 이는 O(n)의 시간이 걸립니다.
   • 따라서 특정 요소를 찾고 제거하기 위해서는 O(n)의 시간이 소요됩니다.
3. 요소 제거 후 힙 재구성:
   • 특정 요소를 제거한 후, 힙 속성을 유지하기 위해 힙을 재구성하는 작업이 필요합니다. 이는 O(log n)의 시간이 걸립니다.
   • 결과적으로, 특정 요소를 제거하는 전체 과정은 O(n) + O(log n) = O(n)의 시간 복잡도를 갖습니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        
        // 오름차순으로 정렬되는 우선순위 큐 생성
        PriorityQueue<Integer> minPq = new PriorityQueue<>();
        // 내림차순으로 정렬되는 우선순위 큐 생성
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
        
        // 주어진 모든 연산을 처리
        for (String operation : operations) {
            // 연산을 공백을 기준으로 분리하여 명령과 값을 추출
            String[] instruction = operation.split(" ");
            
            // 명령이 'I'인 경우 값을 두 개의 우선순위 큐에 추가
            if (instruction[0].equals("I")) {
                int value = Integer.parseInt(instruction[1]);
                minPq.add(value);
                maxPq.add(value);
            }
            // 명령이 'D -1'인 경우 최소값을 삭제
            else if (!minPq.isEmpty() && instruction[1].equals("-1")) {
                maxPq.remove(minPq.poll());
            }
            // 명령이 'D 1'인 경우 최대값을 삭제
            else if (!maxPq.isEmpty() && instruction[1].equals("1")) {
                minPq.remove(maxPq.poll());
            }
        }
        
        // 모든 연산이 끝난 후 우선순위 큐가 비어있는 경우
        if (minPq.isEmpty() && maxPq.isEmpty()) {
            return new int[] {0, 0};
        }
        
        // 최댓값과 최솟값을 반환
        return new int[] {maxPq.poll(), minPq.poll()};
    }
}