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

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

풀이

1. 우선순위큐 두 개 사용 - 오름차순 / 내림차순
2. 명령어가 I 이면 두 큐에 삽입
3. 명령어가 D 이면
   3-1. 숫자가 1 이면 최댓값 삭제 ➡️ 내림차순 큐에서 poll() 하고, 오름차순 큐에서도 같은 요소를 삭제
   3-2. 숫자가 -1 이면 최솟값 삭제 ➡️ 오름차순 큐에서 poll() 하고, 내림차순 큐에서도 같은 요소를 삭제

❗️우선순위큐에서는 삭제가 한 방향에서만 이루어지기 때문에 두 개의 큐를 만들어서 최대, 최솟값을 찾고 동기화 시켜야 함
❗️remove() 메소드를 적절히 사용하자

코드

import java.util.*;

public class DoublePriorityQueue {
	public int[] solution(String[] operations) {
		PriorityQueue<Integer> minQueue = new PriorityQueue<>();                            // 오름차순
		PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());  // 내림차순

		for (String oper : operations) {
			String command = oper.split(" ")[0];
			int num = Integer.parseInt(oper.split(" ")[1]);
			if (command.equals("I")) {
				minQueue.offer(num);
				maxQueue.offer(num);
			}
			else if (num == 1 && !maxQueue.isEmpty()) {
				minQueue.remove(maxQueue.poll());
			}
			else if (num == -1 && !minQueue.isEmpty()){
				maxQueue.remove(minQueue.poll());
			}
		}
		int[] result = new int[2];
		result[0] = !maxQueue.isEmpty() ? maxQueue.poll() : 0;
		result[1] = !minQueue.isEmpty() ? minQueue.poll() : 0;
		return result;
	}

	public static void main(String[] args) {
		DoublePriorityQueue doublePriorityQueue = new DoublePriorityQueue();
		System.out.println(Arrays.toString(doublePriorityQueue.solution(new String[]{"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"})));  // [0, 0]
		System.out.println(Arrays.toString(doublePriorityQueue.solution(new String[]{"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"}))); // [333, -45]
	}
}