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

💜 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

---

🧐 PriorityQueue(우선순위 큐) in Java

자료구조 중 하나

일반적인 큐처럼 선입선출(FIFO)인데, 여기에 우선순위 조건이 추가된 자료구조이다.

즉, 데이터가 들어올때마다 우선순위에 맞게 알아서 정렬되고 우선순위가 높은 것을 먼저 보내는 구조!

따라서, 우선순위 큐를 구현할 때는 반드시 Comparator 또는 Comparable 인터페이스를 구현 해야 한다. 

Compatator과 Comparable의 차이는 이곳을 클릭

(구현하지 않으면 낮은숫자 우선순위가 default)

import java.util.PriorityQueue;
import java.util.Collections;

// 낮은숫자 우선순위
PriorityQueue<Integer> priorityQueueDefault = new PriorityQueue<>();

// 높은숫자 우선순위
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

// Comparable을 이용한 사용자 정의 (람다식)
PriorityQueue<Integer> priorityQueueComparable = new PriorityQueue<>((a, b) -> {
	int first = Math.abs(a);
    int second = Math.abs(b);
    
    if(first == second)	return (a > b ? 1 : -1);
 	else	return first - second;
});

// Compatator을 이용한 사용자 정의 
PriorityQueue<Integer> priorityQueueComparator = new PriorityQueue<>(new Comparator<Student>() {
    @Override
    public int compare(int a, int b) {
       return a - b;	// 오름차순
    }
});

---

📝 풀이

1. 문제 이름 처럼 우선순위큐를 두개 선언하여 풀면 된다.
2. 낮은 숫자 우선순위큐(pqLow), 높은 숫자 우선순위큐(pqHigh)
3. 연산 조건에 따라 최솟값과 최댓값을 삭제한다.
4. 연산이 끝난 후, 우선순위큐 둘 중에 하나라도 비어있으면 {0, 0}을, 아니면 {최댓값, 최솟값}을 반환한다.

---

	import java.util.Arrays;
	import java.util.Collections;
	import java.util.PriorityQueue;

	class Solution {
    	public int[] solution(String[] operations) {
        	int[] answer = {};

			PriorityQueue pqLow = new PriorityQueue<>();    
			PriorityQueue pqHigh = new PriorityQueue<>(Collections.reverseOrder());    

			for (String operation : operations) {
				String o = operation.split(" ")[0];
				int n = Integer.parseInt(operation.split(" ")[1]);

				if (o.equals("I")) {
					pqLow.add(n);
					pqHigh.add(n);
				} else if (o.equals("D")) {
					if (pqLow.isEmpty() || pqHigh.isEmpty())
						continue;

					if (n < 0) {
						int min = pqLow.poll();
						pqHigh.remove(min);
					} else {
						int max = pqHigh.poll();
						pqLow.remove(max);
					}
				}
			}

			if (pqLow.isEmpty() || pqHigh.isEmpty()) {    // 둘중에 하나만 비어있는지 확인해도 상관없지만 둘다 적어주었다.
				answer = new int[] {0, 0};
			} else {
				answer = new int[] {pqHigh.poll(), pqLow.poll()};
			}

			return answer;
    	}
	}
}