[Programmers] 이중우선순위큐

난이도 : Level 3

문제링크

• 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
  • I 숫자 : 큐에 주어진 숫자를 삽입합니다.
  • D 1 : 큐에서 최댓값을 삭제합니다.
  • D -1 : 큐에서 최솟값을 삭제합니다.
• 모든 연산을 처리한 후
  • 큐가 비어있으면 [0,0] 리턴
  • 비어있지 않으면 [최댓값, 최솟값] 리턴

 

해설

1. 두개의 우선순위 큐 사용하기 - 최대힙, 최소힙 

PriorityQueue<Integer> minPq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());

• 최소힙 - 최솟값을 항상 루트로 두는 힙 자료구조
• 최대힙 - 최댓값을 항상 루트로 두는 힙 자료구조

 

2. 삽입

for (String operation : operations) {
    String[] op = operation.split(" ");            
    if (op[0].equals("I")) {
        int num = Integer.parseInt(op[1]);
        minPq.offer(num);
        maxPq.offer(num);
    }
    
    // ...
}

•  "I" 명령어를 처리합니다.
• 최소힙, 최대힙에 각각 노드를 추가합니다

 

3. 제거

for (String operation : operations) {
    String[] op = operation.split(" ");            
	
    // ...
    
    if (op[0].equals("D")) {
        if (minPq.size() == 0) continue;
        if (op[1].equals("-1")) { // 최솟값
            maxPq.remove(minPq.poll());
        } else if (op[1].equals("1")) { // 최댓값
            minPq.remove(maxPq.poll());
        }
    }    
}

• "D" 명령어를 처리합니다.
  • 제거할 노드가 없으면 삭제연산을 건너뜁니다.
  • 최댓값을 삭제할 경우
    • 최대힙에서 루트 노드 제거
    • 최소힙에서 최댓값 제거
  • 최솟값을 삭제할 경우
    • 최소힙에서 루트 노드 제거
    • 최대힙에서 최솟값 제거