들어가며

이중우선순위큐

힙을 이용한 대표적인 테크닉인 이중우선순위큐 문제입니다.

문제설명

이중 우선순위 큐란 숫자를 삽입하는 insert연산, 그리고 최댓값/최솟값을 제거하거나 리턴하는 delete_max_value/delete_min_value연산을 할 수 있는 자료구조입니다. 최대 1,000,000개의 연산이 주어졌을 때, 모든 연산을 처리한 후 큐가 비어있으면 [0, 0], 비어있지 않으면 [최댓값, 최솟값]을 리턴하는 solution함수를 구현하세요.

해설

이중 우선순위 큐는 다음과 같은 개념을 알고 있으면 풀 수 있습니다.

•

힙 자료구조

•

Max-Heap, Min-Heap 두 개의 힙 사용하기

•

lazy하게 처리하기

힙 자료구조

먼저 힙 자료구조는 최댓값, 최솟값을 빠르게 찾아내기 위해 고안된 완전이진트리의 일종입니다. 구현은 다음과 같은 힙 속성을 만족해야 합니다.

•

A가 B의 부모노드(parent node)면, A의 키값과 B의 키값 사이에는 대소 관계가 성립한다.

즉, 트리에서 부모-자식 관계에서 대소를 비교해 부모 쪽을 큰 값이 되도록 swap시키면 Max-Heap, 부모 쪽을 작은 값이 되도록 swap시키면 Min-Heap이 됩니다. 사소하지만 중요한 건, 이 대소 관계는 부모-자식 관계에서만 성립하고 두 형제 노드 사이에는 대소 관계가 정해지지 않는다는 것입니다. 만약 배열을 이용해 힙을 구현했을 때, 이를 순서대로 출력하면 전혀 규칙이 없는 것 같은 형태를 가집니다.

Max-Heap, Min-Heap 두 개의 힙 사용하기

이중 우선순위 큐에서는 최댓값을 뽑거나 최솟값을 뽑는 연산을 둘 다 해야 합니다. 즉, [1, 5, 8, 4, 8, 3, 7, 2]과 같은 원소로 구성된 배열이 있을 때, ‘최댓값을 뽑아주세요’하면 8을 빠르게 뽑고, ‘최솟값을 뽑아주세요’하면 1를 빠르게 뽑아야 합니다. 이를 위해 최댓값을 빠르게 뽑기 위해 부모 노드를 가장 큰 값이 되도록 heapify한 Max-Heap, 최솟값을 빠르게 뽑기 위해 부모 노드를 가장 작은 값이 되도록 heapify한 Min-Heap 두 가지 힙을 사용합니다.

lazy하게 처리하기

하지만 한 가지 문제가 있습니다. 최댓값이나 최솟값을 뽑기 위해 Max-Heap, Min-Heap 중 하나의 힙으로부터 값을 뽑았다면, 다른 힙에서도 찾아서 삭제해주어 동기화해야 합니다. 그렇지 않으면 이상한 결과를 얻을 수 있습니다. 예를 들어, [1, 2, 3] 배열이 있을 때, Max-Heap에서 최댓값을 세 번 뽑았다면 다음과 같은 결과가 됩니다.

•

Max-Heap []

•

Min-Heap [1, 2, 3]

그리고 최솟값을 뽑아야 한다고 하면 어떻게 될까요? 3개의 원소가 들어있는 배열에서 3개의 값을 뽑았으므로 실제 배열에는 값이 없어야 하지만, Min-Heap에는 값이 그대로 남아있기 때문에 1이 뽑힐 것입니다. 말이 되지 않죠. 그러므로 원하는 결과를 얻기 위해서는 [1, 2, 3] 배열에서 최댓값을 뽑을 때, 다음과 같이 되어야 합니다.

•

Max-Heap [1, 2]

•

Min-Heap [1, 2]

그렇다면 한 쪽으로부터 값을 뽑았다면 다른 한 쪽 힙을 전부 뒤져가면서 해당 값을 찾아야 할까요? 그건 너무 비효율적입니다. 따라서 값을 뽑을 때, ‘이 값은 배열로부터 제거되었다’만 표시해주고 실제 이 값에 대한 평가가 필요할 때 비로소 제거하는 lazy한 접근을 사용합니다. 표시를 위해 하나의 변수가 더 필요한 것이죠. 다시 위의 예를 가져오면 다음과 같습니다.

•

Max-Heap [(1, 제거 안됨), (2, 제거 안됨)]

•

Min-Heap [(1, 제거 안됨), (2, 제거 안됨), (3, 제거됨)]

이렇게 해놓고 추후에 Min-Heap에서 최솟값을 뽑을 때, 만약 뽑은 값이 이미 ‘제거됨’이라면 버리고 ‘제거 안됨’인 값을 찾아내면 됩니다.

코드

Node 클래스에는 이 노드가 이미 삭제된 노드인지 판단하기 위한 isDeleted 변수가 있습니다. 이를 이용해 이미 삭제된 값인지를 판단합니다. 그리고 delete() 메서드에서 while문을 통해 isDeleted 변수가 false인 값을 찾을 때까지 뽑아냅니다. false인 값을 찾았다면 이것이 바로 아직 삭제되지 않고 배열에 남아있는 값이 되겠죠.

또, 모든 연산이 끝나고 난 뒤에도 바로 값을 뽑는 것이 아니라 한번 더 while문을 돌려서 실제 존재하는 값만을 찾아내야 합니다.

import java.util.*;

class Node {
    int data;
    boolean isDeleted;

    public Node(int data) {
        this.data = data;
    }
}

class Solution {
    static int number;
    static PriorityQueue<Node> minQueue = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node a, Node b) {
            return Integer.compare(a.data, b.data);
        }
    });
    static PriorityQueue<Node> maxQueue = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node a, Node b) {
            return Integer.compare(b.data, a.data);
        }
    });

    public int[] solution(String[] operations) {
        int[] answer = new int[2];

        for (String op : operations) {
            StringTokenizer st = new StringTokenizer(op);
            String com = st.nextToken();

            switch (com) {
                case "I":
                    insert(Integer.parseInt(st.nextToken()));
                    break;
                case "D":
                    delete(Integer.parseInt(st.nextToken()));
                    break;
            }
        }

        if (number == 0) return new int[] {0 , 0};

        Node minNode = minQueue.poll();

        while (minNode != null && minNode.isDeleted) {
            minNode = minQueue.poll();
        }

        Node maxNode = maxQueue.poll();

        while (maxNode != null && maxNode.isDeleted) {
            maxNode = maxQueue.poll();
        }

        return new int[] {maxNode.data, minNode.data};
    }

    public void insert(int data) {
        Node node = new Node(data);
        minQueue.add(node);
        maxQueue.add(node);
        number++;
    }

    public void delete(int minMax) {
        if (minMax == 1) { // 최댓값 삭제
            Node candidate = maxQueue.poll();

            while (candidate != null && candidate.isDeleted) {
                candidate = maxQueue.poll();
            }

            if (candidate == null) return;

            candidate.isDeleted = true;
        } else { // 최솟값 삭제
            Node candidate = minQueue.poll();

            while (candidate != null && candidate.isDeleted) {
                candidate = minQueue.poll();
            }

            if (candidate == null) return;

            candidate.isDeleted = true;
        }

        number--;
    }
}