2022.02.13 50일차

백준 1927번 (최소 힙)

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다

나의 풀이

1. PriorityQueue 활용하기(기본적으로 최소힙, 내림차순)
2. 값이 0이 아니면 우선순위 큐에 값 추가
3. 값이 0이지만 비어있으면 0출력
4. 값이 0이고 비어있지 않으면 우순순위 큐에 poll(첫번째 값)활용해서 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num != 0) {
                priorityQueue.add(num);
            } else if (priorityQueue.isEmpty()) {
                System.out.println(0);
            } else  {
                System.out.println(priorityQueue.poll());
            }
        }

    }
}

생각하기

• 힙과 이진 탐색 트리의 공통점과 차이점
  - 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리
  - 차이점 :
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음(힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음)
  • 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
• 오름차순 정렬

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a)