문제 출처

코딩테스트 연습 > 힙(Heap) > 이중우선순위큐
https://school.programmers.co.kr/learn/courses/30/lessons/42628

문제 설명

이중우선순위 큐는 3가지의 명령을 받는다.
I 숫자 -> 큐에 주어진 숫자 삽입
D 1 -> 큐에서 최댓값을 삭제
D -1 -> 큐에서 최솟값을 삭제
큐가 할 연산들이 String 형태로 들어있는 operations 배열이 있다.
배열의 모든 연산들을 처리하고 큐가 비어있으면 [0,0]을 return
비어있지 않으면 [최댓값, 최솟값]을 return 하라.

접근 방법

작은 수부터 정렬하는 우선순위 큐 min_pq 와 큰 수부터 정렬하는 우선순위 큐 max_pq 를 2가지 만든다.
이 후, operations 명령들을 수행한다.

명령이 "D 1"으로 시작하면 min_pq에서 max_pq.peek()을 삭제하고, 명령이 "D -1"으로 시작하면 max_pq에서 min_pq.peek()을 삭제한다.
마지막으로 삽입하는 명령의 경우 숫자부분을 substring으로 추출하여 두 우선순위 큐에 더한다.

이후 두 큐가 비어있지 않으면 answer에 각각 최댓값, 최솟값을 넣어 return 한다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        
        PriorityQueue<Integer> min_pq = new PriorityQueue<>();
        PriorityQueue<Integer> max_pq = new PriorityQueue<>(Collections.reverseOrder()); // 최대값이 앞에 오게 정렬
        
        for(String op : operations){
            if(op.startsWith("D 1")){
                min_pq.remove(max_pq.peek());
                max_pq.poll();
                
            }else if(op.startsWith("D -1")){
                max_pq.remove(min_pq.peek());
                min_pq.poll();
            }else{
                int num = Integer.parseInt(op.substring(2));
                min_pq.add(num);
                max_pq.add(num);
            }
        }
        
        if(!min_pq.isEmpty() && !max_pq.isEmpty()){
            answer[0] = max_pq.poll();
            answer[1] = min_pq.poll();
        }
        return answer;
}
}

알게된 점

문제를 처음 접했을 때, 최소,최대 우선순위 큐를 사용해서 푸는 것과과 Deque를 사용해서 푸는 것에 대해서 한참을 생각했다.
우선순위 큐를 사용해서 푸는 것은 일단 삽입 명령은 두개의 큐에 전부 삽입하고, 삭제 명령의 경우 D 1은 최대 큐만, D -1은 최소 큐만 삭제하는 방식으로 접근 했었다. 하지만, 이 방법은 마지막에 '큐가 비어있으면 [0,0]'을 만족시키기가 어려웠다.
그리고 Deque를 쓰는 방법을 생각했지만, 조건이 까다롭고 최솟값과 최댓값 중간인 값들에 대한 처리가 어려웠다.

그래서 답과 비슷하게 풀 뻔했지만, 결국 풀지 못하고 답을 참고했다.
일단 풀이를 할 땐, 접근방식을 정했으면 그 방법대로 풀고 나서 시간복잡도를 다시 생각하는 방법으로 접근해야겠다.

% reverseOrder()은 큰 값이 앞으로 오게함.
설정 검색하여 삭제할 땐, remove() 이용. + poll(), remove() 사용시 큐가 비어있고 반환할 것이 아니면 그냥 넘어간다.

문제푼 흔적