[Python/Java] 백준 1927번 - 최소 힙

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

1927번: 최소 힙

 

혼자 힘으로 풀었는가? : (Python - O / Java - X)

알고리즘 유형
 - 자료 구조
 - 우선순위 큐
 - 힙

문제

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

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

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

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

---

문제 이름 그대로 최소 힙에 관한 문제이다.

(Python 코드)

import sys
input = sys.stdin.readline

import heapq
n = int(input())
q = []
for _ in range(n):
  a = int(input())
  if a == 0:
    if q:
      print(heapq.heappop(q))
    else:
      print(0)
  else:
    heapq.heappush(q, a)

파이썬은 heapq 라이브러리를 이용하여 간단하게 풀 수 있었다.

 

---

(Java 코드)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	
	static List<Integer> heap;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		heap = new ArrayList<Integer>();
		heap.add(0);
		
		for(int i=0; i<n; i++) {
			int a = Integer.parseInt(br.readLine());
			if(a == 0) {
				if(heap.size() == 1) {
					System.out.println("0");
				} else {
					peak();
				}
			} else {
				add(a);
			}
			
			//System.out.println(heap);
		}
	}
	
	private static void peak() {
		int del_item = heap.get(1);
		System.out.println(del_item);
		
		heap.set(1, heap.get(heap.size()-1));
		heap.set(heap.size()-1, del_item);
		heap.remove(heap.size()-1);
		
		int position = 1;
		while( (position*2) < heap.size() ) {
			int min = heap.get(position*2);
			int min_pos = position*2;
			
			if( position*2+1 < heap.size() ) {
				int right = heap.get(position*2+1);
				if( min > right ) {
					min = right;
					min_pos += 1;
				}
			}
			
			if(min > heap.get(position) ) {
				break;
			}
			
			int tmp = heap.get(position);
			heap.set(position, heap.get(min_pos));
			heap.set(min_pos, tmp);
			position = min_pos;
		}
	}

	public static void add(int num) {
		heap.add(num);
		swap(num);
	}

	private static void swap(int num) {
		int now_index = heap.size()-1;
		while(now_index > 1 && heap.get(now_index/2) > num) {
			heap.set(now_index, heap.get(now_index/2));
			heap.set(now_index/2, num);
			now_index /= 2;
		}
	}
}

자바의 경우는 배열을 이용한 heap 자료구조를 이용하여 풀었다.

 

자세한 힙 자료구조에 대한 설명은

 

2022.11.22 - [Language/Java] - [Java] 힙(Heap)

 

위 글을 참고하도록 하자.

 

백준 1927번 - 최소 힙.py

백준 1927번 - 최소 힙.java