백준 7662 풀이

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

이중 우선순위 큐

개요

우선 순위 큐야 유명하니 설명을 넘어가고 이중 우선 순위 큐를 구현해야한다.

삽입은 우선 순위 큐와 동작이 동일하나, 삭제는 큐에서 최대값 또는 최소값을 빼낼 수 있어야 한다.

정렬된 큐에서 최대 또는 최소를 찾을 때 O(n)이 걸리기때문에 삭제 또한 O(n)이다.
처음에 시간 제한을 고려하지않고 코드를 작성해서 제출했지만 '시간 초과'를 만났다. 선형 구조로 이루어진 자료구조에서 탐색에 시간초과가 나왔다면 O(n)보다 적게 드는 O(logn)을 갖는 구조로 바꿔야한다.
대표적으로는 트리가 있다.

풀이 과정

자바 라이브러리 중 TreeSet과 TreeMap은 레드블랙트리로 구성되어 있어 시간복잡도가 O(logn)이다.

TreeSet과 TreeMap이 레드블랙 트리로 구현되어 있다는 것을 알고 있었고 레드블랙 트리 특성상 삽입과 삭제 시 자동으로 정렬이 되기때문에 문제에 적합하다고 판단이 되었다. 물론 우선순위 큐 2개를 구현해서 하나는 오름차순, 하나는 내림차순으로 정렬하여 구현해도 되지만, 두 개의 큐를 동기화하는 과정에서 결국 시간이 더 드는 것 같아 레드블랙 트리를 사용했다.

처음에는 TreeSet을 이용해서 구현했다. 예제는 무리없이 동작을 했다. 하지만 Set 특성상 중복된 값을 허락하지 않기때문에 중복된 값이 들어올 경우 예외가 발생한다.

마찬가지로 TreeMap 또한 key의 중복을 허락하지 않는다. 그래서 처음에는 key는 삽입할 때마다 1씩 증가시키고 value에 입력값을 저장했다. 하지만 정렬은 key값에 따르기때문에 value의 최소, 최대를 찾는데 시간복잡도가 O(n)이다.

그래서 key에 입력값을 넣어야는데 TreeMap도 마찬가지로 key가 중복될 경우 덮어쓴다. 이 부분을 해결해야 올바르게 풀이가 가능하다.

value에 특정한 값을 넣고 key가 중복일 경우 value를 1증가한 값을 저장하자.
그리고 삭제할 때 해당 값이 key의 시작값보다 크면 value를 감소시켜 다시 저장하고 시작값과 같으면 remove해주자.

위와 같은 방식을 생각했고 TreeMap을 이용해서 문제의 조건에 맞는 이중 우선 순위 큐를 구현했다.

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

public class Main {
    static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[] dy = {1, -1, 0, 0, 1, 1, -1, -1};
    static boolean visit[][];
    static int t, k;
    static int graph[][];
    static int land[][];


    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String first = br.readLine();
        t = Integer.parseInt(first);
        for (int i = 0; i < t; i++) {
            k = Integer.parseInt(br.readLine());
            TreeMap<Long, Long> set = new TreeMap<>();
            for (int j = 0; j < k; j++) {
                Long key = 0L;
                String[] line = br.readLine().split(" ");
                long n = Long.parseLong(line[1]);
                if (line[0].equals("I")) {
                    if (set.containsKey(n))
                        set.put(n, set.get(n) + 1);
                    else
                        set.put(n, key);
                } else if (line[0].equals("D")) {
                    if (set.isEmpty()) {
                        continue;
                    }
                    if (n == -1) {
                        long min = set.firstKey();
                        long next = set.get(min) - 1;
                        //중복이 없다
                        if (next < 0)
                            set.remove(min);
                        //중복이 있을 경우 next 를 감소시켜 중복을 제거,
                        //자바의 맵은 키의 중복을 허락하지 않음, 중복된 키 값이 들어올 경우 나중의 값으로 덮어씀
                        //c++에서 multimap 은 중복이 허락된다.
                        else
                            set.put(min, next);
                    } else if (n == 1) {
                        long max = set.lastKey();
                        long next = set.get(max) - 1;
                        if (next < 0)
                            set.remove(max);
                        else
                            set.put(max, next);
                    }
                }
            }
            if (set.isEmpty())
                bw.write("EMPTY\n");
            else {
                bw.write(set.lastKey() + " " + set.firstKey() + "\n");
            }
        }
        br.close();
        bw.close();
    }

}