이중 우선순위 큐

이중 우선순위 큐

백준 7662번 문제

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

 

 

1. 문제

 

 

2. 풀이

아쉽게도 JAVA에는 이중 우선순위 큐가 없기 때문에 직접 만들어줘야 한다.

다행히 우선순위 큐는 존재하기 때문에 이를 토대로 이중 우선순위 큐를 구현하면 된다.

 

먼저 우선순위 큐가 존재하기 때문에 최댓값과 최솟값에 대한 두 개의 우선순위 큐를 만들다.

이중 우선순위 큐에 값을 넣을 때는 두개의 우선순위 큐에 모두 값을 넣어준다.

 

[이중 우선순위 큐 값 추가 예시]

public static class DualPriorityQueue{
    Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
    Queue<Integer> minQueue = new PriorityQueue<>();

    public void add(int number) {
        maxQueue.add(number);
        minQueue.add(number);
    }
}

 

 

이중 우선순위 큐에서 값을 뺄 때는 지정된 한쪽 Queue에서 값을 빼고 다른 쪽에서 그 값을 빼줘 맞춰준다.

 

[이중 우선순위 큐 값 추출 예시]

public static class DualPriorityQueue{
    Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
    Queue<Integer> minQueue = new PriorityQueue<>();

    public void add(int number) {
        maxQueue.add(number);
        minQueue.add(number);
    }

    private int pollMax() {
        Integer maxNumber = maxQueue.poll();
        minQueue.remove(maxNumber);
        return maxNumber;
    }

    private int pollMin() {
        Integer minNumber = minQueue.poll();
        minQueue.remove(minNumber);
        return minNumber;
    }
}

 

값을 뺄 경우 다른 쪽 Queue에 숫자를 맞춰주기 위해서 값을 제거해 줄 때 remove를 사용하였다.

우선순위 큐는 우선순위를 반영해 값을 빼는 것은 빠르지만 remove를 사용하게 되면 구조상 특정 값을 찾고 지워야 하기 때문에 시간이 오래 걸리게 된다.

얼마나 오래 걸리냐면 이 문제에서 remove를 사용해서 이중 우선순위 큐를 구현하면 시간초과가 날 정도로 오래 걸리게 된다.

 

하지만 remove를 사용하지 않으면 지정된 Queue에서만 값을 빼게 되고 두 Queue 사이에 값의 갯수가 맞춰지지 않게 된다.

이를 해결하기 위해서는 이중 우선순위 큐에 들어있는 숫자들을 실질적으로 보관하는 새로운 자료구조를 추가해야 한다.

 

여기서는 Map을 사용해서 이중 우선순위 큐에 저장되는 숫자들의 정보를 저장한다.

 

[이중 우선순위 큐 Map]

public static class DualPriorityQueue{
    Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
    Queue<Integer> minQueue = new PriorityQueue<>();
    Map<Integer, Integer> countMap = new HashMap<>();
}

 

key값은 저장된 숫자를, value는 숫자의 개수(같은 숫자가 여러 개 있을 수 있기 때문)를 의미한다.

 

이제 countMap이 이중 우선순위 큐의 실질적인 숫자를 보관하는 곳이고 나머지 우선순위 큐들은 여기서 값을 넣고 빼기 위한 보조라고 생각하면 된다.

 

이렇게 만들어진 이중 우선순위 큐에서 값을 빼는 경우는 다음과 같이 정리할 수 있다.

 

1. Queue에서 뺀 값이 Map에 있는 경우

다음과 같은 상황에서 최댓값을 뺀다고 해보자

 

[이중 우선순위 큐 예시 그_1]

countMap에는 16과 1만 있기 때문에 maxQueue에 있는 -523은 실질적으로 이중 우선순위 큐에 없는 값이라 생각할 수 있다.

중요한 것은 이처럼 Map에 있는 값과 각 우선순위 큐에 있는 값이 상이하기 때문에 이를 체크해주어야 한다는 것이다.

 

최댓값을 빼야하니 우선 maxQueue에서 최대값을 뺀다.

 

[이중 우선순위 큐 예시 그_2]

 

가장 앞에 있는 16이 빠질 것이고 countMap에도 16이 1개 존재하니 실제로 이중 우선순위 큐에 해당 값이 있다는 뜻이된다.

최댓값 우선순위 큐에서 값을 뺐으니 당연히 이중 우선순위 큐에서 16은 최댓값이 된다.

 

이중 우선순위 큐에서 16을 뺀것이니 countMap에도 이를 반영해 준다.

 

[이중 우선순위 큐 예시 그_3]

 

 

2. Queue에서 뺀 값이 Map에 2개 이상으로 표기되는 경우

다음과 같은 상황에서 최댓값을 뺀다고 해보자

 

[이중 우선순위 큐 예시 그_4]

 

위와 같이 maxQueue에서 가장 앞에 있는 16이 빠질 것이고 countMap에도 해당 값이 존재하는 상황이다.

그런데 value에 2라고 저장되어 있다.

이는 이중 우선순위 큐에 16이 2개 저장되어 있다는 뜻이다.

해당 값을 한 개 뺀 거 기 때문에 value에서 1을 차감해 주면 된다.

 

[이중 우선순위 큐 예시 그_5]

 

3. Queue에서 뺀 값이 Map에 없을 경우

다음과 같은 경우에 최댓값을 뺀다고 해보자

 

[이중 우선순위 큐 예시 그_6]

 

maxQueue에서 가장 앞에 있는 값은 45인데 해당 값은 countMap에 존재하지 않는다.

minQueue에서 값이 먼저 빠졌을 경우 countMap에 해당 값이 지워지는데 maxQueue에서는 값이 빠지지 않기 때문에 이런 현상이 발생한다. 

 

45는 countMap에 존재하지 않기 때문에 계속해서 다음값을 뽑는다.

 

[이중 우선순위 큐 예시 그_7]

 

계속해서 다음값을 빼면 3이 나온다.

하지만 3역 시 countMap에는 존재하지 않기 때문에 실질적으로 이중 우선순위 큐에는 없는 값이다.

따라서 계속해서 다음 값을 뽑는다.

 

[이중 우선순위 큐 예시 그_8]

 

다음 값은 2로 countMap에 존재한다.

이제까지 했었던 것처럼 countMap에서 해당 값을 빼주면 된다.

 

[이중 우선순위 큐 예시 그_9]

 

중요한 것은 이중 우선순위 큐에 저장되는 실질적인 값은 countMap에 있기 때문에 이를 기준으로 두 우선순위 큐에서 값을 빼주면 된다는 것이다.

 

위의 일련의 과정을 토대로 이중 우선순위 큐를 코드로 구현하면 다음과 같다.

 

[DualPriorityQueue]

public static class DualPriorityQueue{
    Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
    Queue<Integer> minQueue = new PriorityQueue<>();
    Map<Integer, Integer> countMap = new HashMap<>();

    public void add(int number) {
        maxQueue.add(number);
        minQueue.add(number);
        countMap.put(number, countMap.getOrDefault(number, 0) + 1);
    }

    private int poll(Queue<Integer> queue) {
        int result = 0;

        while (true) {
            Integer number = queue.poll(); //지정된 Queue에서 값을 뺀다
            //Map에 Queue에 해당하는 값이 존재하면 value(개수)를 반환하고 없다면 0을 반환한다. 
            Integer count = countMap.getOrDefault(number, 0); 

            if (count == 0) { //Map에 Queue에서 뺀값이 없을 경우 Queue에서 값을 빼는 작업을 반복한다.
                continue;
            }
            if (count == 1) {
                countMap.remove(number);
            } else {
                countMap.put(number, count - 1);
            }
            result = number;
            break;

        }

        return result;
    }

    public int pollMax() {
        return poll(maxQueue);
    }

    public int pollMin() {
        return poll(minQueue);
    }
}

 

 

3. 전체 코드

[DualPriorityQueue]

public static class DualPriorityQueue{
    Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
    Queue<Integer> minQueue = new PriorityQueue<>();
    Map<Integer, Integer> countMap = new HashMap<>();

    public void add(int number) {
        maxQueue.add(number);
        minQueue.add(number);
        countMap.put(number, countMap.getOrDefault(number, 0) + 1);
    }

    private int poll(Queue<Integer> queue) {
        int result = 0;

        while (true) {
            Integer number = queue.poll();
            Integer count = countMap.getOrDefault(number, 0);

            if (count == 0) {
                continue;
            }
            if (count == 1) {
                countMap.remove(number);
            } else {
                countMap.put(number, count - 1);
            }
            result = number;
            break;

        }

        return result;
    }

    public int pollMax() {
        return poll(maxQueue);
    }

    public int pollMin() {
        return poll(minQueue);
    }

    public boolean isEmpty() {
        return countMap.isEmpty();
    }
}

 

 

[calculateQueue]

public static void calculateQueue(DualPriorityQueue queue, String command, int number) {
    switch (command) {
        case "I" :
            queue.add(number);
            break;
        case "D" :
            if (queue.isEmpty()) {
                return;
            }
            if (number == 1) {
                queue.pollMax();
            } else if (number == -1) {
                queue.pollMin();
            }
    }
}

 

입력에 따라 이중 우선순위 큐에 값을 추가하거나 빼는 연산을 하는 메서드

 

[main]

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int testSize = Integer.parseInt(br.readLine());

    for (int i = 0; i < testSize; i++) {
        int size = Integer.parseInt(br.readLine());

        DualPriorityQueue queue = new DualPriorityQueue();

        for (int j = 0; j < size; j++) {
            //입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            String commend = st.nextToken();
            int number = Integer.parseInt(st.nextToken());

            //로직
            calculateQueue(queue, commend, number);
        }

        //출력
        if (queue.isEmpty()) {
            bw.write("EMPTY");
        } else {
            int result = queue.pollMax();
            bw.write(String.format("%d ", result));
            if (!queue.isEmpty()) {
                result = queue.pollMin();
            }
            bw.write(String.format("%d", result));
        }
        bw.flush();
        bw.newLine();
    }
}

 

마지막에 값을 출력하기 위해 이중 우선순위 큐에서 값을 빼야 한다.

만약 이중 우선순위 큐에 값이 단 한 개만 존재할 경우 최솟값과 최댓값은 동일하다.

그런데 값을 출력하기 위해 최댓값을 먼저 빼버리면 countMap이 비어버리고 최솟값을 뺄 수 없다.

이 경우에는 어차피 이중 우선순위 큐에 값은 하나 남아있고 최대 최솟값이 동일하니 앞에서 뺀 최댓값을 최솟값으로 사용하면 된다.

 

[전체 코드]

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

public class 이중_우선순위_큐_7662_2 {

    public static class DualPriorityQueue{
        Queue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
        Queue<Integer> minQueue = new PriorityQueue<>();
        Map<Integer, Integer> countMap = new HashMap<>();

        public void add(int number) {
            maxQueue.add(number);
            minQueue.add(number);
            countMap.put(number, countMap.getOrDefault(number, 0) + 1);
        }

        private int poll(Queue<Integer> queue) {
            int result = 0;

            while (true) {
                Integer number = queue.poll();
                Integer count = countMap.getOrDefault(number, 0);

                if (count == 0) {
                    continue;
                }
                if (count == 1) {
                    countMap.remove(number);
                } else {
                    countMap.put(number, count - 1);
                }
                result = number;
                break;

            }

            return result;
        }

        public int pollMax() {
            return poll(maxQueue);
        }

        public int pollMin() {
            return poll(minQueue);
        }

        public boolean isEmpty() {
            return countMap.isEmpty();
        }
    }

    public static void calculateQueue(DualPriorityQueue queue, String command, int number) {
        switch (command) {
            case "I" :
                queue.add(number);
                break;
            case "D" :
                if (queue.isEmpty()) {
                    return;
                }
                if (number == 1) {
                    queue.pollMax();
                } else if (number == -1) {
                    queue.pollMin();
                }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int testSize = Integer.parseInt(br.readLine());

        for (int i = 0; i < testSize; i++) {
            int size = Integer.parseInt(br.readLine());

            DualPriorityQueue queue = new DualPriorityQueue();

            for (int j = 0; j < size; j++) {
                //입력
                StringTokenizer st = new StringTokenizer(br.readLine());
                String commend = st.nextToken();
                int number = Integer.parseInt(st.nextToken());

                //로직
                calculateQueue(queue, commend, number);
            }

            //출력
            if (queue.isEmpty()) {
                bw.write("EMPTY");
            } else {
                int result = queue.pollMax();
                bw.write(String.format("%d ", result));
                if (!queue.isEmpty()) {
                    result = queue.pollMin();
                }
                bw.write(String.format("%d", result));
            }
            bw.flush();
            bw.newLine();
        }
    }
}