[백준] 1927번 최소힙

park geonwoo·2024년 9월 24일

목록 보기

11/32

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

풀이

이 문제는 최소 힙 자료구조를 활용하여, 삽입 및 최소값 제거 연산을 처리하는 문제입니다. 최소 힙은 항상 가장 작은 값이 루트에 위치하는 이진 트리 구조로, 삽입과 삭제 모두 평균적으로 O(log n)의 시간 복잡도를 가집니다. 이 문제에서는 주어진 연산을 효율적으로 처리하는 것이 목표입니다.

문제 해결 전략

문제의 요구사항:
- 자연수 x가 입력되면, 이를 힙에 추가합니다.
- x = 0이 입력되면, 힙에서 가장 작은 값을 출력하고 그 값을 제거합니다. 만약 힙이 비어 있다면 0을 출력합니다.
자료구조 선택:
- 최소값을 빠르게 찾고 삭제하는 문제이므로, 우선순위 큐(Priority Queue) 자료구조를 사용합니다. 자바에서는 PriorityQueue 클래스가 최소 힙의 특성을 갖고 있어 매우 적합합니다.
우선순위 큐의 동작:
- 삽입 연산: 값을 힙에 삽입하는 연산으로, 삽입 후 힙의 구조를 유지하기 위해 O(log n) 시간이 소요됩니다.
- 삭제 연산: 힙에서 가장 작은 값을 제거하는 연산으로, 마찬가지로 O(log n) 시간이 소요됩니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 연산의 개수
        int N = Integer.parseInt(br.readLine());
        
        // 최소 힙을 위한 우선순위 큐 사용
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            
            if (x == 0) {
                // x가 0이면 최소값 출력 및 제거
                if (minHeap.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(minHeap.poll()).append("\n");
                }
            } else {
                // 자연수 x일 경우 최소 힙에 추가
                minHeap.add(x);
            }
        }
        
        // 결과 출력
        System.out.println(sb);
    }
}

코드 설명

입력 처리:
- BufferedReader를 사용해 입력을 처리하고, 입력된 값을 int형으로 변환합니다.
- StringBuilder를 사용하여 결과를 누적하여 출력 속도를 최적화합니다.
우선순위 큐(PriorityQueue):
- PriorityQueue는 자바의 최소 힙 구현체입니다. 내부적으로 최소값이 자동으로 정렬되며, 삽입과 삭제가 모두 O(log n) 시간에 처리됩니다.
- x = 0이 입력되면 힙이 비어 있는지 확인하고, 비어 있으면 0을 출력합니다. 그렇지 않으면 minHeap.poll()을 통해 가장 작은 값을 출력하고 힙에서 제거합니다.
- x > 0인 경우는 자연수를 힙에 삽입하는데, 이는 minHeap.add(x)로 처리됩니다.
결과 출력:
- 출력할 값들을 StringBuilder에 저장한 후, 마지막에 한 번에 출력하여 성능을 최적화합니다.

시간 복잡도 분석

삽입 연산 (x > 0):
- 자연수 x를 힙에 삽입하는 연산은 O(log n) 시간이 소요됩니다. 힙에 삽입된 값의 개수에 따라 힙을 재정렬하는 작업이 필요하기 때문입니다.
삭제 연산 (x == 0):
- x == 0일 때, 최소값을 꺼내고 힙에서 제거하는 연산 역시 O(log n) 시간이 소요됩니다. 이 경우 힙의 루트에서 가장 작은 값을 제거한 후, 나머지 요소들이 다시 정렬됩니다.
전체 시간 복잡도:
- 입력 크기 N에 대해 각 연산은 삽입과 삭제 모두 O(log n)의 시간이 걸립니다.
- 따라서 최악의 경우 시간 복잡도는 O(N log N)이 됩니다. 여기서 N은 최대 100,000이므로, 이 시간 복잡도는 문제를 해결하는 데 충분히 효율적입니다.

공간 복잡도 분석

입력 데이터:
- BufferedReader를 사용해 입력을 처리하며, O(N) 크기의 입력을 처리할 공간이 필요합니다.
우선순위 큐:
- 최소 힙을 저장하는 PriorityQueue는 최대 N개의 값을 저장하므로, 공간 복잡도는 O(N)입니다.
출력 데이터:
- 출력에 사용되는 StringBuilder 역시 최대 N개의 값을 저장할 수 있으므로, 공간 복잡도는 O(N)입니다.