메모

/*
1. 비어있는 배열 -> [ ]
2. 배열에 자연수 x 를 넣는다. -> [x1, x2, x3 ...]
3. 배열에서 가장 큰 값을 출력 + 그 값을 배열에서 제거 -> [x1, x3 ...] 출력: x2

N = 연산의 개수

정수 x = 연산에 대한 정보를 나타내는 정수
	x가 자연수라면 : 배열에 x라는 값을 넣는(추가하는) 연산	(단, 입력되는 자연수는 231보다 작다)
    x가 0이라면 : 배열에서 가장 큰 값을 출력 + 그 값을 배열에서 제거
*/

---

해결법

방법 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		// BufferedReader
        
        int N = Integer.parseInt(br.readLine());		// 형 변환

        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());		// 내림차순 정렬
        
        StringBuilder sb = new StringBuilder();		// StringBuilder
        
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());		// 형 변환

            if (num == 0) {			// 0을 넣을 경우
                sb.append(que.size() == 0 ? 0 : que.poll()).append('\n');		// 배열이 비어있을 경우 : true면 0, false면 poll
            } else {		// 0 이 아닐 경우, 수를 추가한다
            	que.add(num);
            }    
        }
        
        System.out.println(sb.toString());		// 문자열로 반환하여 출력
    }
}

• heap(힙)

  참고: 운영체제 (OS) - (2) 프로세스의 메모리 영역 (메모리 구조)

• PriorityQueue

  참고: 자바 컬렉션 (Java Collection, 컬렉션 프레임워크) - (4) Queue

• Collections.reverseOrder()

  • PriorityQueue는 기본적으로 오름차순 정렬이기 때문에, 내림차순으로 변경하면 배열 [0]이 가장 큰 값이 된다.

출력을 할 때, queue의 size = 0이라면 배열이 비어있는 경우이므로, 0을 출력해준다.

• poll()

  • 내림차순으로 정렬했기에 가능함

  참고: LIFO (후입선출), 호출 스택, FIFO (선입선출)

• toString()

  참고: toString()

---

최대 힙 (백준 11279번)