[lv.3] 이중 우선순위 큐

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

• 문제
  위 그대로다. 우선순위 큐인데 앞 뒤로 뺄 수 있게 해라.

• 풀이
  오름차순 큐와 내림차순 큐를 만든다.
  이후 삽입일 경우 둘다 추가.
  삭제일 경우 먼저 명령에 맞는 큐에서 poll()한 뒤 다른 큐에서 remove(제거값)을 실행한다.
  만일 수행하기 전 큐가 비어있으면 이는 무시한다.

• 소감
  remove(val)란 함수가 있었구나...
  하지만 이 함수, 조금 많이 성능이 떨어진다고 한다.
  만일 시간제한이 빡빡했으면 통과 불가일듯.
  TreeMap, 즉 자료구조 하나로만 풀 수도 있으니 밑의 코드를 참조.

• 코드 (우선순위 큐 2개)

import java.util.*;

class Solution {
    public int[] solution(String[] cmd) {
        int[] answer = new int[2];
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        StringTokenizer st;
        for(int i=0; i<cmd.length; i++){
            st = new StringTokenizer(cmd[i]);
            String oper = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
            if(oper.equals("I")){
                maxQ.add(num);
                minQ.add(num);
            }
            else{
                if(num==1){
                    if(!maxQ.isEmpty()){
                        int del = maxQ.poll();
                        minQ.remove(del);
                    }
                }
                else{
                    if(!minQ.isEmpty()){
                        int del = minQ.poll();
                        maxQ.remove(del);
                    }
                }
            }
        }
        if(!maxQ.isEmpty()){
            answer[0] = maxQ.poll();
            answer[1] = minQ.poll();
        }
        return answer;
    }
}

• 코드 (트리맵, 백준)

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

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        int n;
        String cmd;
        int itg;
        for(int i=0; i<t; i++){
            TreeMap<Integer, Integer> map = new TreeMap<>();
            n = Integer.parseInt(br.readLine());
            for(int j=0; j<n; j++){
                st = new StringTokenizer(br.readLine(), " ");
                cmd = st.nextToken();
                itg = Integer.parseInt(st.nextToken());
                if(cmd.equals("I")){
                    map.put(itg, map.getOrDefault(itg,0)+1);
                }
                else{
                    if(itg==1){
                        if(map.size()==0) continue;
                        int temp = map.get(map.lastKey());
                        if(temp==1){
                            map.remove(map.lastKey());
                        }
                        else{
                            map.put(map.lastKey(), temp-1);
                        }
                    }
                    else{
                        if(map.size()==0) continue;
                        int temp = map.get(map.firstKey());
                        if(temp==1){
                            map.remove(map.firstKey());
                        }
                        else{
                            map.put(map.firstKey(), temp-1);
                        }
                    }
                }
            }
            if(map.size()==0){
                System.out.println("EMPTY");
            }
            else{
                System.out.println(map.lastKey()+" "+map.firstKey());
            }
        }
    }
}