[백준] 11279 : 최대 힙 - 우선순위 큐(Priority Queue)

문제 출처: https://www.acmicpc.net/problem/11279

---

문제

 

---

시도

 

처음엔 문제 카테고리를 신경 쓰지 않고 내가 생각해본 LinkedList를 통해 풀어보기로 했다.

LinkedList 삽입, 삭제가 자유롭고, 조회에 대한 시간 복잡도가 O(n)이라는 단점이 있지만 문제는 가장 큰 요소, 즉 첫 번째 요소를 출력할 걸 요구하기 때문에 문제가 없을 거라고 여겼다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

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

        StringBuilder sb = new StringBuilder();
        LinkedList<Integer> list = new LinkedList<>();
        while(n-- > 0) {
            int k = Integer.parseInt(br.readLine());

            if(k == 0) {
            	sb.append(list.isEmpty() ? "0" : list.removeFirst()).append("\n");
            }
            else {
                if(list.isEmpty()) list.add(k);
                else {
                    for(Integer num : list) {
                        if(k > num) {
                            list.add(list.indexOf(num), k);
                            break;
                        }
                    }
                }
            }
        }

        System.out.print(sb);
    }
}

 

코딩 고수는 내가 LinkedList를 언급한 순간부터 결과를 예측했을 것 같다.

맞다. 시간 초과로 실패했다.

 

아무래도 0이 아닌 수가 입력되었을 때, 기존 linkedlist의 어디에 값을 새로 넣을지 찾는 반복문이 발목을 잡은 것 같다.

 

참고 출처: 자바 LinkedList 구조 & 사용법 - 정복하기

---

풀이

 

해당 문제는 백준에서 미리 분류된 것처럼 우선순위 큐 Priority Queue로 푸는 문제였다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        
        while(n-- > 0) {
            int k = Integer.parseInt(br.readLine());
            
            if(k == 0) {
                sb.append(pq.isEmpty() ? "0" : pq.poll()).append("\n");
            } else {
                pq.offer(k);
            }
        }
        
        System.out.print(sb);
    }
}

 

가장 중요했던 부분은 PriorityQueue 자체에 정렬 옵션을 제공하여 삽입하면 바로 정렬이 일어나도록 하는 것이 관건이었던 것 같다.

 

풀이 출처: [백준/BOJ] 11279 : 최대 힙 (JAVA / 자바)

---

알게 된 점

 

풀이는 무력하게 틀렸지만 그대로 넘어가면 아무 교훈도 없을 것 같아 우선순위 큐에 대해 정리해보려고 한다. 

 

정의

우선순위 큐는 일반적인 큐의 구조인 First In First Out을 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아니라 우선순위를 먼저 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

 

데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행됩니다.

(※ 최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙)

 

특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조로, 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 합니다. 
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이뤄집니다.
3. 내부 구조가 힙으로 구성되어 있기 때문에 시간 복잡도는 O(N logN)입니다.
4. 우선순위를 중요시해야 하는 상황에서 주로 쓰입니다.

 

 

참고 출처: [Java] Priority Queue (우선 순위 큐)