문제 7662번(성공)

소스코드(우선순위 큐 사용)

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class boj7662 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        while(t >0){
            int k = Integer.parseInt(br.readLine());
            PriorityQueue<Integer> pqDown = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            PriorityQueue<Integer> pqUP = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            for (int i = 0; i < k; i++) {
                String[] operations = br.readLine().split(" ");
                int num = Integer.parseInt(operations[1]);
                switch(operations[0]){
                    case "I":
                        pqUP.offer(num);
                        pqDown.offer(num);
                        break;
                    case "D":
                        if(!pqUP.isEmpty()){
                            if(num == -1){
                                int del = pqUP.poll();
                                pqDown.remove(del);
                            }else{
                                int del = pqDown.poll();
                                pqUP.remove(del);
                            }
                        }
                        break;
                }
            }
            if(pqUP.isEmpty()){
                sb.append("EMPTY\n");
            }else{
                sb.append(pqDown.peek() + " " + pqUP.peek() +"\n");
            }
            t--;
        }
        System.out.println(sb);
    }
}

소스코드(TreeMap사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class boj7662ver2 {
    public static void main(String[] args )throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        while(t >0) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                String operations = st.nextToken();
                int num = Integer.parseInt(st.nextToken());
                switch (operations) {
                    case "I":
                        treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
                        break;
                    case "D":
                        if (treeMap.isEmpty()) break;
                        if (num == -1) {
                            int minKey = treeMap.firstKey();
                            if (treeMap.get(minKey) == 1) {
                                treeMap.remove(minKey);
                            } else {
                                treeMap.put(minKey, treeMap.get(minKey) - 1);
                            }
                        } else {
                            int maxKey = treeMap.lastKey();
                            if (treeMap.get(maxKey) == 1) {
                                treeMap.remove(maxKey);
                            } else {
                                treeMap.put(maxKey, treeMap.get(maxKey) - 1);
                            }
                        }
                        break;
                }
            }
            if(treeMap.isEmpty()){
                sb.append("EMPTY \n");
            }else{
                sb.append(treeMap.lastKey() + " " + treeMap.firstKey() +"\n");
            }
            t--;
        }
        System.out.println(sb);
    }
}

풀이 접근

1. 문제 이름과 같이 우선순위 큐를 사용하기로 한다.
   1-1. 우선순위 큐를 오름차순과 내림차순 2가지를 만든다. 1-2. I의 경우 두 개의 우선순위 큐에 추가하고, D의 경우 우선순위 큐가 비어있지 않으면 num이 -1일 경우 오름차순에서 poll(최대값)한 값을 내림차순에서도 remove, num이 1일 경우에는 내림차순에서 poll(최소값)한 값을 오름차순에 remove한다.
   1-3. 큐가 비어 있을 경우에는 EMPTY를, 아닐 경우에는 내림차순 peek(최대값) + 오름차순 peek(최소값)을 출력한다.
2. 이중 우선순위 큐를 사용하기 위해 treemap을 사용한 경우
   2-1. Treemap(값, 해당 값의 개수)를 생성한다.
   2-2. value 값을 put하고 싶을 때, map에서 사용되는 메소드로 해당 값이 treemap에 없으면 0을 반환하고, 있으면 해당 value를 반환하는 getOrDefault 메소드를 이용한다. 2-3. I의 경우 treemap에 추가하고 D의 경우 treemap이 비어 있다면 패스, num이 -1일 때는 treemap의 firstkey를 가져오고 해당 키 값이 1일 때는 treemap에서 제거하지만, 1이 아닐 경우에는 해당 키에 대한 값을 1 줄인다. num이 1일 경우에는 앞에와 비슷하게 lastkey를 가져오고 비교해서 제거 또는 줄이는 방법을 실시한다.
   2-4. treemap이 비어 있을 경우에는 EMPTY를, 아닐 경우에는 내림차순 peek(최대값) + 오름차순 peek(최소값)을 출력한다.

문제 핵심

• 우선순위 큐에 대한 이해
• 이중 우선순위 큐를 구현하기 위해 treemap 혹은 map을 사용할 수 있는지!