[Java] 백준 풀기 1927 - 최소 힙

자바 백준 1927번

실버 2

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

1927번: 최소 힙

 

 

 

 

 

문제 보기

분류: 자료 구조, 우선순위 큐

 

 

 

 

 

문제 풀기

메서드 분리를 위해 명령을 모두 배열에 저장한다.

 

우선순위 큐를 기본 옵션으로 생성하여 낮은 숫자가 부여되도록한다.

명령어를 하나씩 빼내어 0 또는 그 외의 자연수에 대한 조건문을 실행한다.

0 일 경우 배열이 비어있는지 확인하고 비었다면 0 을 출력, 그렇지 않으면 poll() 을 통해 가장 작은 값을 출력하고 제거한다.

그 외, 자연수의 명령어일 경우 그 수를 minHeap 에 add() 를 사용하여 추가한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();  // N 입력

        // 입력되는 명령들을 배열에 저장
        int[] operations = new int[N];
        for (int i = 0; i < N; i++) {
            operations[i] = sc.nextInt();  // 명령 입력
        }

        // 명령 시행
        processOperations(N, operations);
    }

    public static void processOperations(int N, int[] operations) {
        // 우선순위 큐를 사용. 우선 순위를 낮은 숫자 순으로 부여.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 각 명령어를 순차적으로 실행
        for (int i = 0; i < N; i++) {
            int x = operations[i];

            if (x == 0) {
                if (minHeap.isEmpty()) {
                    // 배열이 비어 있는 경우
                    System.out.println(0);
                } else {
                    // 그 외 가장 작은 값을 출력하고 제거
                    System.out.println(minHeap.poll());
                }
            } else {
                // 자연수를 배열에 추가
                minHeap.add(x);
            }
        }
    }
    
}