[백준] 7662 이중 우선순위 큐 java

이중 우선순위 큐 구현 문제였다.

 

min-heap 과 max-heap 두개로 구현해볼까 했는데 뭔가 내가 전혀 모르는 방법이 있을 것 같아서 찾아보니 min-max-heap을 구현하는 방법과 c++의 STL 라이브러리에서 Multiset을 이용한 방법 그리고 내가 사용한 TreeMap을 이용한 구현 방법이 있었다. 

 

먼저 나는 다른 알고리즘 문제를 풀면서 Map 자료구조 중에서는 항상 HashMap 만을 사용해왔었다. 

 

TreeMap은 내부가 레드 블랙 트리를 사용하고 있고 삽입, 삭제, 추가 모두 O(log n)의 시간복잡도가 나와서 HashMap 보다는 성능이 떨어진다. 하지만 범위의 검색을 하거나 최댓값, 최솟값을 찾을 때는 TreeMap을 사용하는 것이 효율적이다.

 

처음에는 구현할 때 중복으로 들어오는 값을 생각을 못하고 구현했다가 문제를 잘 보니 중복되는 수가 들어올 수 있다는 문구를 발견했다. 역시 처음에 문제를 볼 때 한번에 정확한 요구사항을 체크하는 습관을 만들어야겠다.

 

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static int T;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.print(sb.toString());
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
    }

    static void solve() throws IOException{
        for(int i = 1; i <= T; i++) {
            TreeMap<Long,Integer> q = new TreeMap<>();
            final int N = Integer.parseInt(br.readLine());
            for(int j = 1; j <= N; j++) {
                st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                long val = Long.parseLong(st.nextToken());

                if(command.equals("I")) push(q, val);
                else if(command.equals("D")) {
                    if(q.size() == 0) continue;
                    if(val == -1) deleteMin(q);
                    else if(val == 1) deleteMax(q);
                }
            }
            if(q.size() == 0) sb.append("EMPTY");
            else {
                sb.append(q.lastKey()).append(" ").append(q.firstKey());
            }
            if(i != T) sb.append("\n");
        }
    }

    static void push(TreeMap<Long,Integer> q, long val) {
        q.put(val, q.getOrDefault(val, 0)+1);
    }

    static void deleteMax(TreeMap<Long,Integer> q) {
        int maxNum = q.get(q.lastKey());
        if(maxNum > 1) {
            q.replace(q.lastKey(), maxNum, maxNum-1);
        }
        else {
            q.remove(q.lastKey());
        }
    }

    static void deleteMin(TreeMap<Long,Integer> q) {
        int minNum = q.get(q.firstKey());
        if(minNum > 1) {
            q.replace(q.firstKey(), minNum, minNum-1);
        }
        else {
            q.remove(q.firstKey());
        }
    }

}