[Programmers] 이중우선순위큐 - Java

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

프로그래머스

---

1. 문제

각 명령어에 따라 이중우선순위큐의 연산이 처리된다.

I 숫자 => 큐에 숫자 삽입

D 1 => 큐에서 최댓값 삭제

D -1 => 큐에서 최솟값 삭제

최댓값, 최솟값을 return 하되, 큐가 비어있을 경우 [0,0] 을 return한다.

 

2. 풀이

우선순위큐 2개를 사용한다.

하나는 오름차순으로 정렬하는 큐인 최소힙,

다른 하나는 내림차순으로 정렬하는 큐인 최대힙

으로 활용한다.

 

여기서 핵심은 "최소큐와 최대큐의 원소를 동일하게 해줘야 한다"는 것이다.

무슨 말이냐면, 최댓값 삭제하라고 해서 최대힙에서만 poll하면 안된다는 의미이다.

최대힙에서도 삭제해주고 최소힙에서도 삭제해줘야 한다는 것이다.

근데 최대힙에서 삭제하는건 maxPq.poll() 해주면 끝이다. 그럼 최소힙에서는 어떻게 삭제하나?

 

바로 remove 함수를 사용하는 것이다.

pq.remove()는 pq.poll()과 역할이 동일하다. 우선순위큐의 맨 앞 원소를 삭제해준다는 공통점이 있다.

둘의 차이점은 remove()는 큐가 비어있을 경우 Exception이 발생하고, poll()은 null을 반환한다.

 

하지만 특이점이 있다.

pq.remove(원소)를 할 경우, 우선순위 큐에서 해당 원소가 삭제된다.

만약 큐에 해당 원소가 없어도 Exception은 발생하지 않는다. 삭제가 되지 않을 뿐이다.

이러한 달달한 함수를 사용하면 손쉽게 이 문제를 풀 수 있다.

 

3. 코드

연산자가 D이고 큐가 비었을 경우엔 바로 continue해줬다. 밑을 더 볼 필요가 없기 때문이다.

import java.io.*;
import java.util.*;

class Solution {
    
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minPq = new PriorityQueue<> (); // 최소힙
        PriorityQueue<Integer> maxPq = new PriorityQueue<> ((o1, o2) -> o2-o1);
        StringTokenizer st = null;
        
        for (String item : operations) {
            st = new StringTokenizer(item);
            String oper = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
            
            if ("D".equals(oper) && minPq.isEmpty()) {
                continue;
            }
            
            if ("I".equals(oper)) {
                minPq.offer(num);
                maxPq.offer(num);
                continue;
            }
            
            // 최소값 삭제
            if (num < 0) {
                maxPq.remove(minPq.poll());
                continue;
            }
            
            // 최댓값 삭제
            minPq.remove(maxPq.poll());
        }
        
        if (minPq.isEmpty()) {
            return new int[] {0,0};
        }
        
        return new int[] {maxPq.poll(), minPq.poll()};
    }
}

 

4. 사담

우선순위큐를 사용하는 문제는 항상 재밌는 것 같다.

내림차순할 때 항상 람다로 (o1, o2) -> o2-o1을 활용했는데

Collections.reverseOrder()도 있다는걸 잊지말자 !