7662번(이중 우선순위큐)

첫 시도

• Q는 10^6
• 우선순위큐를 2개 만들어 최솟값, 최댓값을 poll()
• 한쪽 큐에서 poll 된 값을 다른쪽 큐에서 remove()
• 답은 잘 나오는데 시간초과 -> O(Q)인데 왜 시간초과?
• 우선순위큐는 힙으로 구현되어 있음, remove()를 하려면 앞에서부터 순차 탐색 -> remove()의 시간복잡도는 O(N) -> 즉, O(Q^2)으로 구현한 것

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소힙 우선순위큐
    static PriorityQueue<Integer> rePq = new PriorityQueue<>(Collections.reverseOrder()); // 최대값 우선순위큐
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while(T != 0){
            int Q = Integer.parseInt(br.readLine());
            for(int i = 0; i < Q; i++){
                String[] input = br.readLine().split(" ");
                if(input[0].equals("I")){ // insert
                    pq.add(Integer.parseInt(input[1]));
                    rePq.add(Integer.parseInt(input[1]));

                }
                else { // delete
                    int num = 0;
                    if(pq.isEmpty()) continue;
                    if(input[1].equals("-1")) {
                        num = pq.poll(); // 최솟값 삭제
                        rePq.remove(num); // 반대쪽 큐에서 해당 숫자 삭제
                    }
                    else {
                        num = rePq.poll(); // 최대값 삭제
                        pq.remove(num); // 반대쪽 큐에서 해당 숫자 삭제
                    }

                }
            }
            Integer max = rePq.poll();
            Integer min = pq.poll();
            if(max == null) sb.append("EMPTY\n");
            else sb.append(max + " " + min + "\n");
            T--;
        }
        System.out.println(sb);
    }
}

해결

• TreeMap을 사용 -> TreeMap은 key를 기준으로 정렬되어 있는 Map
• 또한 Red-Black 트리라는 이진 트리로 구현되어 있음
• 이진 트리는 값 탐색, 삭제, 삽입 시 O(log N)으로 가능
• 시간복잡도는 Q개의 쿼리 처리 * 값 탐색 -> O(Qlog N)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static TreeMap<Integer,Integer> tM;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while(T != 0){
            tM = new TreeMap<>();
            int Q = Integer.parseInt(br.readLine());
            for(int i = 0; i < Q; i++){
                String[] input = br.readLine().split(" ");
                int num = Integer.parseInt(input[1]);
                if(input[0].equals("I")){ // insert
                    // 입력받은 숫자를 key로, 그 숫자의 갯수를 value로
                    tM.put(num, tM.getOrDefault(num,0)+1);
                }
                else { // delete
                    if(tM.size() == 0) continue;
                    // num이 -1이면 최솟값, 1이면 최댓값을 minOrMax에 삽입
                    int minOrMax = num == -1 ? tM.firstKey() : tM.lastKey();
                    int numCount = tM.get(minOrMax); // 최솟값 또는 최댓값의 숫자의 갯수
                    //numCount가 1이면 삭제, 아니라면 value를 -1하고 put
                    if(tM.put(minOrMax,numCount - 1)== 1) tM.remove(minOrMax);
                }
            }
            if(tM.size() == 0) sb.append("EMPTY\n");
            else sb.append(tM.lastKey() + " " + tM.firstKey() + "\n");
            T--;
        }
        System.out.println(sb);
    }
}

참고

• https://girawhale.tistory.com/14