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

풀이 ①

1. 아이디어

1) x > 0 인 경우

• PriorityQueue에 x 추가
  => 최소값이 먼저 오도록 정렬

2) x == 0 인 경우

• PriorityQueue가 not empty
  => PriorityQueue에서 remove 및 출력
• PriorityQueue가 empty
  => 0 출력

2. 자료구조

• PriorityQueue<Integer>: 입력 정수 x 저장 및 정렬

3. 시간 복잡도

• PriorityQueue / Heap 의 시간 복잡도
  => 삽입 / 삭제: O(log n) (n: 노드 개수)
• 최대 총 n번 삽입 / 삭제 발생
  => 대충 최대 n log n
  => n 최대값 대입: 10^5 x log 10^5 = 5 x 10^5 << 1억 (1초)

코드

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

public class Main_PriorityQueue {
	static int n;		// 수행할 연산 개수
	static int x;		// 연산 정보 정수 (0 또는 자연수)
	static PriorityQueue<Integer> pq = new PriorityQueue<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			x = Integer.parseInt(br.readLine());

			if (x > 0)
				pq.add(x);
			else if (x == 0) {
				if (!pq.isEmpty())
					sb.append(pq.remove()).append("\n");
				else
					sb.append(0).append("\n");
			}
		}

		System.out.println(sb.toString());
	}
}

풀이 ②

1. 아이디어

• Min Heap 직접 구현
  => 배열로 구현, add(), remove()
• 루트 노드에 min 값 위치

Min Heap 구현

• Min 노드가 루트 노드 arr[1]에 위치
  (쉬운 구현을 위해 arr[0]은 사용 X)
• 부모, 자식 index 번호 관계
  => 왼쪽 자식의 index = 부모의 index 2
  => 오른쪽 자식의 index = (부모의 index 2) + 1
  => 부모의 index = 자식의 index / 2
  
  
  

1. void add(int item)
   1) 맨 뒤 arr[size+1]에 새로운 item 추가
   2) 새로운 노드 arr[size+1]을 부모 노드들과 비교해가면서 힙 정렬
   => ReHeapification Upward
   
   
   
2. int remove()
   1) 루트 노드 arr[1]을 삭제
   2) 빈 루트 노드 arr[1]를 마지막 노드 arr[size]로 채움
   2) 루트 노드 arr[1] ~ arr[size-1] 까지 내려가면서 부모, 자식 비교해가면서 힙 정렬
   => ReHeapification Downward

2. 자료구조

• MinHeap: 구현한 최소 힙

3. 시간 복잡도

• PriorityQueue / Heap 의 시간 복잡도
  => 삽입 / 삭제: O(log n) (n: 노드 개수)
• 최대 총 n번 삽입 / 삭제 발생
  => 대충 최대 n log n
  => n 최대값 대입: 10^5 x log 10^5 = 5 x 10^5 << 1억 (1초)

코드

import java.io.*;

class MinHeap {
	private int[] arr;		// arr[1 ~ size] 사용
	private int size = 0;

	public MinHeap(int length) {
		arr = new int[length];
	}

	public void add(int item) {
		arr[++size] = item;		// 맨 뒤에 새로운 노드 추가

		// Upward
		for (int i = size; i > 1; i /= 2) {
			if (arr[i / 2] > arr[i])		// 부모 > 자식
				swap(i / 2, i);
			else
				break;
		}
	}

	public int remove() {
		if (size == 0)
			throw new IllegalStateException();

		int root = arr[1];	// 삭제 및 반환할 루트 노드
		arr[1] = arr[size--];	// 빈 루트 노드에 마지막 노드 채움

		// Downward
		for (int i = 1; i * 2 <= size; ) {
			if (arr[i] < arr[i * 2] &&
					arr[i] < arr[i * 2 + 1])	// 부모 < 왼쪽 자식, 오른쪽 자식 => 정렬된 경우
				break;
			else if (arr[i * 2] < arr[i * 2 + 1]) {		// 왼쪽 자식 < 오른쪽 자식
				swap(i, i * 2);		// 더 작은 왼쪽 자식이랑 부모 바꿈
				i = i * 2;
			}
			else {		// 왼쪽 자식 > 오른쪽 자식
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
		}

		return root;
	}

	public boolean isEmpty() { return size == 0; }
	public int size() { return size; }

	private void swap(int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
}


public class Main_DevHeap {
	static int n;			// 연산의 개수
	static int x;			// 자연수 또는 0 입력
	static MinHeap minHeap;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());
		minHeap = new MinHeap(n + 1);

		for (int i = 0; i < n; i++) {
			x = Integer.parseInt(br.readLine());

			if (x > 0)
				minHeap.add(x);
			else if (x == 0) {
				if (!minHeap.isEmpty())
					sb.append(minHeap.remove()).append("\n");
				else
					sb.append(0).append("\n");
			}
		}

		System.out.println(sb.toString());
	}
}