1. 문제에 대하여 📦

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628

(1) 조건 분석 📊

이중 우선순위 큐는 다음 연산이 가능한 자료구조를 의미한다.

I 숫자: 형태의 명령어는 큐에 주어진 숫자를 삽입
D 1: 큐에서 최댓값을 삭제
D -1: 큐에서 최소값을 삭제

2. 코드가 나오기까지 🛠️

KEY WORD: 우선순위 큐, HashMap maxHeap, minHeap

Java에는 최대값과 최소값을 ArrayDeque처럼 머리와 꼬리에서 동시에 뺄 수 있는 자료 구조가 없기 때문에, 우선순위 큐를 두 개 활용하여야 한다.

이때 많은 사람들이 궁금해할 것은 '어떻게 이 둘의 Sync를 맞출 거냐' 는 것일 거다.
만약 숫자 내림차순 큐에서 값을 하나 뺐는데, 그것이 오름차순 큐에서 이미 삭제된 값이라면, 그 값은 무효하므로 더 이상 계산을 진행하면 안되기 때문이다.

필자는 해당 계산을 위해 HashMap을 활용했다.
해시맵은 명부 같은 것이다. (값 삽입 시 등록, 값 삭제 시 삭제) 이를 통해, 두 개의 큐 중 어느 곳에서라도 삭제되면 해시맵 명부에서도 삭제한다. 만약 이미 해시맵 명부에 없는 값이라면, 무효한 값이므로, 최대값이나 최소값을 다시 poll()한다.

(1) 시간복잡도 분석 ⏳

제일 많은 연산횟수가 operation 배열을 한 바퀴 도는 것인데, 해당 배열의 길이는 $1,000,000$ 이므로, 시간 초과 걱정은 없다.

3. 코드 🌐

(1) SUDO CODE 💬

0. 자료구조 세팅: 우선순위 큐 2개(내림차순, 오름차순), 해시맵 (명부 작성용)
1. 다음에 따라 명령어를 하나씩 연산한다.
    1. 삽입 명령이면, 두 개의 큐와 해시맵에 값을 삽입한다.
    2. 최대값 삭제 명령어 이면, HashMap 명부에 존재하는 값을 만날 때까지 poll()한다.
    3. 최소값 삭제 명령어도 똑같이 HashMap 명부에 존재하는 값을 만날 때까지 poll() 한다.
2. 명부를 전부 돈 뒤에도 둘의 sync를 맞추어야 한다. 왜냐하면 삭제 명령어가 최대값 삭제나 최소값 삭제 중 하나로 치우친 경우, 위의 연산 과정이 끝나고, 둘의 sync가 안 맞을수 있기 때문이다.
    1. 1번의 2와 3번을 반복한다.
3. 큐에 값이 남아있으면 그것들의 peek()을 출력, 아니면 `[0,0]` 을 출력한다.

(2) JAVA CODE ☕

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> (b-a));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a,b) -> (a-b));
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < operations.length; i++){
            StringTokenizer st = new StringTokenizer(operations[i]);
            char order = st.nextToken().charAt(0);
            int value = Integer.parseInt(st.nextToken());

            switch (order) {
                case 'I': {
                    maxHeap.add(value);
                    minHeap.add(value);
                    map.put(value, value);
                    break;
                }
                case 'D': {
                    PriorityQueue<Integer> now;
                    if(value == 1){ 
                        now = maxHeap;
                    }else {
                        now = minHeap;
                    }
                    while(now.size() > 0){
                        int out = now.poll();
                        if(map.get(out) != null){
                            map.remove(out);
                            break;
                        }
                    }   
                    break;
                }
            }
        }

        while(maxHeap.size() > 0){
            int peek = maxHeap.peek();
            if(map.get(peek) == null) maxHeap.poll();
            else break;
        }

        while(minHeap.size() > 0) {
            int peek = minHeap.peek();
            if(map.get(peek) == null) minHeap.poll();
            else break;
        }

        if(maxHeap.size() == 0 && minHeap.size() == 0) return new int [] {0,0};
        else return new int [] {maxHeap.peek(), minHeap.peek()};
    }
}