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

문제

---

코드

`PriorityQueue` 이용

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

// queue 두 개 사용
public class bj_7662_1 {
    private static final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private static final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private static final HashMap<Integer, Integer> map = new HashMap<>();

    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());

        for (int i = 0; i < T; i++) {
            int k = Integer.parseInt(br.readLine());
            minHeap.clear();
            maxHeap.clear();
            map.clear();

            for (int j = 0; j < k; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                calculate(st.nextToken(), Integer.parseInt(st.nextToken()));
            }

            if (map.isEmpty()) {
                sb.append("EMPTY").append("\n");
            } else {
                int res = delete(maxHeap);
                sb.append(res).append(" ");
                if (!map.isEmpty()) {
                    res = delete(minHeap);
                }
                sb.append(res).append("\n");
            }
        }

        System.out.println(sb);
    }


    private static void calculate(String letter, int num) {
        if (letter.equals("I")) {
            minHeap.add(num);
            maxHeap.add(num);
            map.put(num, map.getOrDefault(num, 0) + 1);
        } else if (!map.isEmpty()) {
            delete(num == 1 ? maxHeap : minHeap);
        }
    }


    private static int delete(PriorityQueue<Integer> queue) {
        while (!queue.isEmpty()) {
            int num = queue.poll();
            if (map.containsKey(num)) {
                int cnt = map.getOrDefault(num, 0);
                if (cnt == 1) {
                    map.remove(num);
                } else {
                    map.put(num, cnt - 1);
                }
                return num;
            }
        }
        return 0;
    }
}

 

 

`TreeMap` 이용

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

// TreeMap 사용
public class bj_7662_2 {
    private static TreeMap<Integer, Integer> map = new TreeMap<>();

    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());

        for (int i = 0; i < T; i++) {
            int k = Integer.parseInt(br.readLine());
            map = new TreeMap<>();

            for (int j = 0; j < k; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                calculate(st.nextToken(), Integer.parseInt(st.nextToken()));
            }

            if (map.isEmpty()) {
                sb.append("EMPTY");
            } else {
                sb.append(map.lastKey()).append(" ").append(map.firstKey());
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static void calculate(String letter, int num) {
        if (letter.equals("I")) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        } else if (!map.isEmpty()) {
            int delNum = num == 1 ? map.lastKey() : map.firstKey();
            if (map.get(delNum) == 1) {
                map.remove(delNum);
            } else {
                map.put(delNum, map.get(delNum) - 1);
            }

        }

    }
}

 

---

풀이

`PriorityQueue`

처음 했던 코드 - 시간 초과로 실패

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

// queue 두 개 사용
public class bj_7662_1 {
    private static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    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());

        for (int i = 0; i < T; i++) {
            int k = Integer.parseInt(br.readLine());
            minHeap.clear();
            maxHeap.clear();

            for (int j = 0; j < k; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                calculate(st.nextToken(), Integer.parseInt(st.nextToken()));
            }

            if (minHeap.isEmpty()) {
                sb.append("EMPTY").append("\n");
            } else {
                sb.append(maxHeap.poll()).append(" ").append(minHeap.poll()).append("\n");
            }
        }

        System.out.println(sb);
    }


    private static void calculate(String letter, int n) {
        if (letter.equals("I")) {
            minHeap.add(n);
            maxHeap.add(n);
            return;
        }

        if (minHeap.isEmpty() || maxHeap.isEmpty()) {
            return;
        }

        if (n == 1) {
            int max = maxHeap.poll();
            minHeap.remove(max);
        } else {
            int min = minHeap.poll();
            maxHeap.remove(min);
        }


    }
}

• `PriorityQueue`에서 `remove()` 메서드는 큐 내부에서 특정 요소를 찾은 후 이를 제거하기 때문에 시간 복잡도가 O(n)이다. 따라서 큐가 커질 수록 성능이 저하될 수 있다.

→ `HashMap` 도입

 

`calculate` 함수

private static void calculate(String letter, int num) {
    if (letter.equals("I")) {
        minHeap.add(num);
        maxHeap.add(num);
        map.put(num, map.getOrDefault(num, 0) + 1);
    } else if (!map.isEmpty()) {
        delete(num == 1 ? maxHeap : minHeap);
    }
}

• 삽입(`I num`)
  • `minHeap`과 `maxHeap`에 `num` 삽입
  • `map`에 해당 숫자의 개수를 증가시켜 현재 존재하는 개수 기록
• 삭제(`D 1` 또는 `D -1`)
  • `D 1` → `maxHeap`(최대값)에서 삭제
  • `D -1` → `minHeap`(최솟값)에서 삭제
  • `map`이 비어있는 경우 연산 수행X 

 

 

`delete` 함수

private static int delete(PriorityQueue<Integer> queue) {
    while (!queue.isEmpty()) {
        int num = queue.poll();
        if (map.containsKey(num)) {
            int cnt = map.getOrDefault(num, 0);
            if (cnt == 1) {
                map.remove(num);
            } else {
                map.put(num, cnt - 1);
            }
            return num;
        }
    }
    return 0;
}

• 힙에서 숫자를 꺼낸다.
• `map`에 있는 숫자이면:
  • 개수가 1개이면 `map`에서 제거
  • 개수가 2개 이상이면 1감소
• 삭제된 숫자 반환

 

`minHeap`과 `maxHeap`에 값이 남아있더라도, `map`에서 존재하는 값만 유효한 값으로 취급하여 시간 복잡도를 크게 줄일 수 있다.

---

`TreeMap`

`TreeMap`은 자동 정렬 기능이 있는 이진 탐색 트리 기반 맵이다. 따라서 `firstKey()` (최솟값)과 `lastKey()` (최대값)을 O(logN) 시간에 가져올 수 있다.

 

 

`calculate` 함수

private static void calculate(String letter, int num) {
    if (letter.equals("I")) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    } else if (!map.isEmpty()) {
    	int delNum = num == 1 ? map.lastKey() : map.firstKey();
    	if (map.get(delNum) == 1) {
        	map.remove(delNum);
    	} else {
        	map.put(delNum, map.get(delNum) - 1);
        }
    }
}

• 삽입(`I num`)
  • 이미 존재하는 숫자는 개수 증가
  • 없으면 기본값 0을 넣고 +1
• 삭제(`D 1` 또는 `D -1`)
  • 삭제할 숫자가 1개 남아 있으면 완전히 제거
  • 여러 개 있으면 개수만 감소 
    • `D 1` → 최댓값(lastKey)
    • `D -1` →최솟값(firstKey)