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

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

7662번: 이중 우선순위 큐

---

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

public class Main {
    static int T, k, n;
    static String[] cmd;
    static PriorityQueue<Integer> pq, rPq;
    static Map<Integer, Integer> exist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            k = Integer.parseInt(br.readLine());
            pq = new PriorityQueue<>();
            rPq = new PriorityQueue<>(Collections.reverseOrder());
            exist = new HashMap<>();
            while (k-- > 0) {
                cmd = br.readLine().split(" ");
                switch (cmd[0]) {
                    case "I":
                        n = Integer.parseInt(cmd[1]);
                        pq.add(n);
                        rPq.add(n);
                        //map에서 통합 관리
                        if (exist.containsKey(n))
                            exist.put(n, exist.get(n) + 1);
                        else
                            exist.put(n, 1);
                        break;
                    default:
                        if (!pq.isEmpty() && cmd[1].equals("-1")) //최솟값 삭제
                            delete(pq);
                        else if (!rPq.isEmpty() && cmd[1].equals("1")) //최댓값 삭제
                            delete(rPq);
                        break;
                }
            }
            if(exist.isEmpty()) //큐 안이 사실상 빈 경우
                sb.append("EMPTY\n");
            else{
                List<Integer> nums = new ArrayList<>(exist.keySet());
                Collections.sort(nums);
                sb.append(nums.get(nums.size() - 1)).append(" ").append(nums.get(0)).append("\n");
            }
        }
        System.out.println(sb);
    }
    private static void delete(PriorityQueue<Integer> pq) {
        while (!pq.isEmpty()) {
            int min = pq.poll();
            if (exist.containsKey(min)) {
                int cnt = exist.get(min) - 1;
                if (cnt == 0) exist.remove(min);
                else exist.replace(min, exist.get(min) - 1);
            } else continue;
            break;
        }
    }
}

💡 우선순위 큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

거의 동일한 문제를 프로그래머스에서 풀었었음 →  동일하게 2개의 우선순위 큐 정의해 풀었지만 시간 초과 발생...

❓이유
✅ default 문에 break를 안씀
→ 여전히 오류 발생.. remove 연산이 시간복잡도가 큰 것으로 추측.
✅ remove를 사용해 직접 제거하는 대신 map으로 개수 관리해주게 수정해봄
→ 드디어 통과...

풀이

• 최솟값(pq), 최댓값(rPq)을 뽑을 우선순위 큐를 각각 정의함
• 대신 2개의 큐안에 담긴 숫자들을 동기화 해줘야 함
  • 원래는 한 큐에서 poll한 최솟값(or 최댓값)을 나머지 큐에서 remove로 삭제해 줌 → 시간 초과 발생
  • 직접 큐에서 제거하는 것 대신, Map을 사용
• <숫자 : 개수>형태로 Map에 저장해 poll할 때마다 해당 수의 잔여 수량을 확인
  • 1개 이상 존재하면 해당 수를 유효 처리 후, 기록된 개수 -1 해줌
  • 0개인 경우엔 map에서 삭제 시켜줌
• 모든 명령어를 수행한 뒤, map에 남은 key들 == 양쪽 큐에 남아있는 유효 숫자들 이므로 key들을 list로 뽑아 정렬한 뒤 최대, 최솟값을 뽑아 출력함
  • map이 비었음 == 큐가 빔 == EMPTY 출력

➕ map 키가 존재하는지 판별하고, get의 결과가 없다면 미리 지정한 디폴트 값을 반환하는 함수
     ➡️ map.getOrDefault(key, 0)

---

💡 TreeMap 활용 풀이

TreeMap

• 이진 트리 기반으로 오름차순으로 정렬된 형태로, <Key : Value> 객체 저장 
   - 레드-블랙 트리 형태
• 데이터 저장 시 키값으로 즉시 정렬됨
   [유사] TreeSet (그냥 값만 저장)
• 데이터를 저장할 때 즉시 정렬 들어가므로 성능이 HashMap보다 떨어짐
• 대부분 map과 유사한 메서드 구성
  • firstEnrty() : 최소 Entry 출력
  • firstKey() : 최소 Key 출력
  • lastEntry() : 최대 Entry 출력
  • lastKey() : 최대 Key 출력

출처: https://coding-factory.tistory.com/557

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

public class Main {
    static int T, k;
    static String cmd;
    static TreeMap<Integer, Integer> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            k = Integer.parseInt(br.readLine());
            map = new TreeMap<>();
            while (k-- > 0) {
                cmd = br.readLine();
                if(cmd.equals("D -1")){ //최솟값
                    if(!map.isEmpty()) {
                        if (map.firstEntry().getValue() == 1)
                            map.remove(map.firstKey());
                        else map.put(map.firstKey(), map.firstEntry().getValue() - 1);
                    }
                } else if (cmd.equals("D 1")) {
                    if(!map.isEmpty()) {
                        if (map.lastEntry().getValue() == 1)
                            map.remove(map.lastKey());
                        else map.put(map.lastKey(), map.lastEntry().getValue() - 1);
                    }
                }else {
                    int n = Integer.parseInt(cmd.substring(2));
                    map.put(n, map.getOrDefault(n, 0) + 1); //없을 경우 1, 있을 경우 +1
                }
            }
            if(map.isEmpty()) sb.append("EMPTY\n");
            else sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
        }
        System.out.println(sb);
    }
}