백준 7662번 :: 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

1차 시도

접근방법 : 문제 이름에서도 언급했기 때문에 "우선순위 큐"를 써야하나보다! 하고 냅다 PQ부터 만들어주고.

연산에서 최댓값과 최솟값이 필요하기 때문에 우선순위 큐를 두 개 만들어주고 하나는 역으로 정렬해주도록 했다.

그리고 입력값의 경우에 따라 I, D를 입력받을 때로 구분짓고 문제의 요구사항을 맞춰 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            PriorityQueue<Integer> pqMax = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> pqMin = new PriorityQueue<>();
            int k = Integer.parseInt(br.readLine());
            for (int i = 0; i < k; i++) {
                String[] inputs = br.readLine().split(" ");
                String cmd = inputs[0];
                int max = Integer.MIN_VALUE;
                switch (cmd) {
                    case "I":
                        int cmdNum = Integer.parseInt(inputs[1]);
                        if (cmdNum >= max) {
                            pqMax.offer(cmdNum);
                            pqMin.offer(cmdNum);
                        }
                        max = cmdNum;
                        break;
                    case "D":
                        int cmdNum2 = Integer.parseInt(inputs[1]);
                        if (pqMax.isEmpty()) {
                            break;
                        } else if (cmdNum2 == 1) { // 최댓값 삭제
                            pqMin.remove(pqMax.poll());
                            break;
                        } else if (cmdNum2 == -1) { // 최솟값 삭제
                            pqMax.remove(pqMin.poll());
                            break;
                        }
                }
            }
            if (pqMax.isEmpty() && pqMin.isEmpty()) sb.append("EMPTY").append("\n");
            else sb.append(pqMax.peek()).append(" ").append(pqMin.peek()).append("\n");
        }
        System.out.println(sb);
    }
}

그런데.. 시간초과가 났다.

이유를 좀 찾아보니 우선순위 큐에서 remove() 메서드의 시간 복잡도가 O(N)이기 때문이란다.

같이 푼 스터디원이 '트리맵'을 쓰는 방법을 알려줘서 트리맵으로 다시 풀어보았다.. (라고 쓰고 해답을 찾아봄..)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            TreeMap<Integer, Integer> map = new TreeMap<>();
            int k = Integer.parseInt(br.readLine());
            for (int i = 0; i < k; i++) {
                String[] inputs = br.readLine().split(" ");
                String cmd = inputs[0];
                switch (cmd) {
                    case "I":
                        int num = Integer.parseInt(inputs[1]);
                        map.put(num, map.getOrDefault(num, 0) + 1);
                        break;
                    case "D":
                        int cmdNum2 = Integer.parseInt(inputs[1]);
                        if (map.size() == 0) {
                            break;
                        } else {
                            int key = cmdNum2 == 1 ? map.lastKey() : map.firstKey();
                            int cnt = map.get(key);

                            if (cnt == 1) map.remove(key);
                            else map.put(key, cnt - 1);
                        }
                }
            }
            if (map.size() == 0) sb.append("EMPTY").append("\n");
            else sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
        }
        System.out.println(sb);
    }
}

 

다행히 통과...🥲 확실히 골드는 어렵네..