[백준, 자바, 1927번] 최소 힙

풀이

• 해당 문제는 단순히 배열을 사용하여 풀고자 할 경우엔
• 문제가 있다고 판단하여 문제의 타이틀에 나온 것처럼
• 최소 힙 문제 유형이기에 우선순위 큐를 사용하여 문제를 해결.
• 그리고 출력이 많이 되기에 그냥 write하여 한 번에 출력할 수 있도록 하여 해결.

 

import java.io.*;
import java.util.*;
public class _1927 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Queue<Long> li = new PriorityQueue<>();
        int N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            long x = Long.parseLong(br.readLine());
            if (x==0) {
                if (li.isEmpty()) bw.write(0+"\n");
                else bw.write(li.poll()+"\n");
            }
            else li.add(x);
        }
        bw.flush();
    }
}

 

• 여기서 힙이란?
  • 힙(Heap)은 완전 이진 트리 형태의 자료구조로, 다음 두 가지 특성을 가짐.
    • 최소 힙(Min-Heap): 부모 노드가 자식 노드보다 항상 작거나 같은 값을 갖는 구조.
      • 즉, 가장 작은 값이 루트 노드에 위치.
    • 최대 힙(Max-Heap): 부모 노드가 자식 노드보다 항상 크거나 같은 값을 갖는 구조.
      • 즉, 가장 큰 값이 루트 노드에 위치.
    • 따라서 힙은 배열이나 리스트로 구현되며, 주로 우선순위 큐를 구현하는 데 사용됨.
• 그리고 최소 힙이기에 그냥 우선순위 큐를 단순히 사용했으며,
• 만약 최대 힙의 문제였다면 아래처럼 변경해주기

Queue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());

 

• 그리고 힙의 메서드는 다음과 같음
  • 추가
    • add: 맨 뒤에 요소 추가
      • 단, 큐가 꽉 찼을 때는 예외 발생
      • (기본적인 큐는 문제 없지만, 크기를 제한하는 ArrayBlockingQueue의 경우 에러 발생)
    • offer: 맨 뒤에 요소 추가
      • 단, 큐가 꽉 찻을 경우 false 반환
  • 삭제
    • remove: 맨 앞 요소 제거 및 반환
      • 단, 큐가 비어있다면 예외 발생
    • poll: 맨 앞 요소 제거 및 반환
      • 단, 큐가 비어이다면 null 반환
  • 조회(삭제X)
    • element: 큐의 맨 앞 요소 반환
      • 단, 없다면 예외 발생
    • peek: 큐의 맨 앞 요소 반환
      • 단, 없다면 null 반환