(JAVA) 백준 문제 풀이 - 우선순위 큐 단계 - 11279번 최대 힙 (실버 2)

 

이번 문제는 최대 힙을 이용하여 배열에서 가장 높은 값을 출력하고 제거하는 프로그램을 만드는 것이다.

문제를 풀기위해서는 먼저 최대 힙에 대해서 알고 있어야 하는데, 자바에서는 우선순위 큐라는 것을 이용하여 비슷한 형태를 만들 수 있다.

최대 힙에 대해서 궁금하다면 잘 정리된 글이 있으니 참고하기 바란다.

https://innovation123.tistory.com/111

[JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap)

---

우선 순위 큐(Priority Queue)란?

이번 문제를 풀기 위해선 우선 순위 큐라는 것을 아아야 한다.

쉽게 설명하면 선입 선출 구조인 Queue에 우선 순위를 설정하여 우선순위가 높은 순서대로 데이터를 꺼내는 구조이다.

해당 큐에 들어올때 우선 순위가 존재하며, 데이터를 꺼낼때 우선순위가 높은 순서대로 나오고 우선순위가 같은 경우에는 선입선출된 순서로 나온다.

자바의 우선순위 큐는 힙(Heap)  방식으로 구현되어 있다.

 

우선순위 큐 생성

우선 순위 큐를 생성할 때에는 우선 순위를 지정해 주어야 한다.

아무것도 넣지 않으면 기본적으로 오름차순을 따르게 되어 있지만 만약 다른 조건을 사용하여 우선순위를 정하고 싶다면 이전에 정렬에서 사용했던 것처럼 Comparable 인터페이스를 구현하거나, 생성시에 Comparator를 매개변수로 넣어주거나, 매개변수에 람다식을 작성하는 방식으로 우선순위를 지정해야 한다.

 

먼저 기본적으로 생성하는 코드는 다음과 같다.

PriorityQueue<Integer> queue = new PriorityQueue<>();

기본적으로 Queue의 형태를 따르므로 형식 지정이 가능하며 선언시에는 PriorityQueue로 선언해주면 된다.

이 경우 기본적인 정렬 방식인 오름차순을 따르며 큐에 값이 들어갈 때 우선 순위인 오름차순에 따라 순서가 결정되며 우선순위가 같은 경우 먼저 들어온 순으로 빠져 나가게 된다.

 

반대로 내림차순으로 우선순위를 지정해 주고 싶다면 다음과 같이 Comparator를 매개변수로 넣어 주면 된다.

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

정렬 단계에서 정렬 조건을 정해주던 그 코드와 동일한 것을 볼 수 있다.

 

다시 정리해보면 우선순위 큐란 결국 정렬 순서를 정해주면 해당 정렬순서에 따라 큐에 집어 넣고 정렬 순서가 같다면 선입선출된 방식으로 요소를 빼낼수 있는 자료 구조라고 생각하면 되겠다.

그럼 이제 문제를 풀어보며 실제로 사용해 보도록 하자.

---

import java.io.*;
import java.nio.Buffer;
import java.util.*;

class Main {

    public static int n;
    public static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> d = new PriorityQueue<>(Collections.reverseOrder());
        sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int m = Integer.parseInt(br.readLine());
            if (m == 0) {
                if (d.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(d.poll()).append("\n");
                }
            } else {
                d.add(m);
            }
        }

        System.out.println(sb);
    }
}

문제에서 관건은 정렬 순서를 어떻게 바꿔 주느냐이므로 나는 Collections.reverseOrder()메서드를 사용하여 역순으로 정렬하여 내림차순을 구현하였다.

물론 당연히 앞서 설명한대로 Comparator를 구현하여 풀어도 된다.

import java.io.*;
import java.nio.Buffer;
import java.util.*;

class Main {

    public static int n;
    public static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> d = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int m = Integer.parseInt(br.readLine());
            if (m == 0) {
                if (d.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(d.poll()).append("\n");
                }
            } else {
                d.add(m);
            }
        }

        System.out.println(sb);
    }
}

 

 

위쪽이 Comparator를 통해 구현한 것이고 아래쪽이 Collections.reverseorder() 메서드를 통해 구현한 것이다.

둘다 잘 작동하는 것을 알 수 있다.

 

추가적으로 바로 밑에 최소 힙을 구하는 문제도 있는데 위 코드에서 앞서 설명한 우선순위 조건만 바꿔주면 된다.

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

1927번: 최소 힙

import java.io.*;
import java.nio.Buffer;
import java.util.*;

class Main {

    public static int n;
    public static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> d = new PriorityQueue<>();
        sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int m = Integer.parseInt(br.readLine());
            if (m == 0) {
                if (d.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(d.poll()).append("\n");
                }
            } else {
                d.add(m);
            }
        }

        System.out.println(sb);
    }
}

코드를 보면 크게 어려운 것이 없다. 

우선순위 큐의 기본 순서는 오름차순이므로 특별한 조건 없이 우선순위 큐를 생성하고, 입력 받은 값은 add를 통해 큐에 집어 넣은 뒤 입력값이 0이면 큐가 비어있는 경우 0을, 아닌경우 poll을 통해 최대값을 출력해 내면 된다.

---

참고자료

https://innovation123.tistory.com/111

[JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap)

https://innovation123.tistory.com/112