자바(백준) 7662 이중 우선순위 큐

오답 노트 & 새로 알게 된 점

해당 문제를 풀면서 정말 스트레스를 많이 받았다.

하지만 그만큼 얻는 것이 많은 문제였다.

 

이 문제를 풀지 못해 구글링을 해서 힌트를 얻었는데 계속 96퍼에서 틀렸다고 나오는 것이다.

그래서 왜 틀렸는지 오카방에 물어봐서 해결할 수 있었다.

 

우선순위 큐를 사용하면서 최대 힙을 만들기 위해 람다식으로 return o2 - o1을 했는데 여기서 문제가 생겼다.

문제에서 32비트 정수 즉, int 범위의 끝에서 끝까지를 말했다. 근데 여기서 o2 - o1을 하면 오버 플로우가 난다.

그래서 제대로 된 최대 힙을 만들 수 없었다. 

그래서 앞으로는 o2.compareTo(o1)을 자주 사용할 것이다..

 

위 문제를 해결하고 나서 다른 코드들을 보았는데 TreeMap을 사용하여 너무나 쉽게 풀었다.

TreeMap이란 키 기준으로 정렬하면서 Tree를 이루는데 뭐 레드 블랙 트리로 이뤄져있고 등등 있는데 

궁금하신 분은 잘 찾아서 공부하시면 될 것 같다!!

 

TreeMap을 공식문서에서 보니 lastKey와 firstKey로 각각 Map의 key중에 가장 큰 값, 가장 작은 값을 get할 수 있었던 것이다.

그리고 심지어 삭제할 때도 remove하나로 O(1)만에 해결이 된다.. 

만약 우선순위 큐 안에서 remove를 하게 된다면 O(N)이었을 것이다..

 

그래서 TreeMap을 사용하면 최대 힙, 최소 힙을 이용한 우선순위 큐 2개를 만들고 + hashmap을 만들 필요가 없어진다..

 

이번에 TreeMap을 제대로 공부해서 꼭 다음에는 써먹어야겠다.

 

---

코드1 (PriorityQueue)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static PriorityQueue<Integer> pq_asc;
    static  PriorityQueue<Integer> pq_desc;
    static HashMap<Integer, Integer> hm;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int test_case = atoi(br.readLine());
 
        for (int test = 0; test < test_case; test++) {
 
            pq_asc = new PriorityQueue<>((o1,o2)->{
                return o2.compareTo(o1);
            }); //내림차순 --> 최대힙
 
 
            pq_desc = new PriorityQueue<>(); //오름차순 --> 최소힙
 
            hm = new HashMap<>();
 
            int N = atoi(br.readLine());
            int max = 0, min = 0;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String cmd = st.nextToken();
                int order = atoi(st.nextToken());
 
                if(cmd.equals("I")) {
                    hm.put(order, hm.getOrDefault(order, 0) + 1);
 
                    pq_asc.offer(order);
                    pq_desc.offer(order);
                }
                else{
                    if(hm.size() == 0) continue;
 
                    removeQ(order);
                }
            }
 
            if(hm.size() == 0) System.out.println("EMPTY");
            else{
                max = removeQ(1);
 
                if(hm.size() > 0) min = removeQ(-1);
                else min = max;
 
                System.out.println(max + " " + min);
            }
        }
    }
 
    static int removeQ(int cmd) {
        int num = 0;
        if(cmd == 1){ //pq_asc에서 뺏음
            while (true) {
                num = pq_asc.poll();
 
                int cnt = hm.getOrDefault(num, 0);
 
                if(cnt == 0) continue;
 
                if(cnt == 1) hm.remove(num);
                else hm.put(num, cnt - 1);
 
                break;
            }
        }
        else{
            while (true) {
                num = pq_desc.poll();
 
                int cnt = hm.getOrDefault(num, 0);
 
                if(cnt == 0) continue;
 
                if(cnt == 1) hm.remove(num);
                else hm.put(num, cnt - 1);
 
                break;
            }
        }
        return num;
    }
}

 

코드2 ( TreeMap )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static TreeMap<Integer, Integer> hm = new TreeMap<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int test_case = atoi(br.readLine());
 
        for (int test = 0; test < test_case; test++) {
            int n = atoi(br.readLine());
            int s1 = 0, s2 = 0;
            hm.clear();
 
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String cmd = st.nextToken();
                int order = atoi(st.nextToken());
 
                if(cmd.equals("I")){
                    hm.put(order, hm.getOrDefault(order, 0) + 1);
                }
                else{
                    if(hm.isEmpty()) continue;
 
                    int num = 0;
                    if(order == 1){
                        num = hm.lastKey();
                    }
                    else{
                        num = hm.firstKey();
                    }
 
//                    int cnt = hm.get(num);
//
//                    if(cnt == 1) hm.remove(num);
//                    else hm.put(num, cnt - 1);
                    
                    if(hm.put(num, hm.get(num) - 1) == 1) hm.remove(num);
                    
                    //put은 value를 반환함
                }
            }
 
            if(hm.isEmpty()) System.out.println("EMPTY");
            else{
                System.out.println(hm.lastKey() + " " + hm.firstKey());
            }
        }
    }
}