[백준] 최소 힙 - 1927 (java)

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

---

최소힙을 구현하는 문제다
일단 그냥 사용하기 편한 ArrayList로 구현해 보았다

오답 1 - 시간초과

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	// 연산의 개수
		
		List<Integer> heap = new ArrayList<>();
		
		for (int n = 0; n < N; n++) {
			int command = sc.nextInt();
			if (command == 0) {		// 배열에서 가장 작은 수 출력, 제거
				if (heap.isEmpty()) {	// 배열이 비었다면
					System.out.println(0);
				} else {	// 최솟값 출력, 제거
					System.out.println(heap.get(0));
					heap.remove(0);
				}
			} else {	// 2^31 보다 작은 자연수
				heap.add(command);
				Collections.sort(heap);
			}	
		}
	}

}

라고 하길래 ArrayList를 PriorityQueue로 바꿔보았다

오답2 - 시간초과

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	// 연산의 개수	// N(1 ≤ N ≤ 100,000)
		
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		
		for (int n = 0; n < N; n++) {
			int command = sc.nextInt();
			if (command == 0) {		// 배열에서 가장 작은 수 출력, 제거
				if (heap.isEmpty()) {	// 배열이 비었다면
					System.out.println(0);
				} else {	// 최솟값 출력, 제거
					System.out.println(heap.poll());
				}
			} else {	// 2^31 보다 작은 자연수
				heap.add(command);
			}	
		}
	}
}

그래도 시간초과가 났다.

최후의 방법으로 Scanner 대신 BufferedReader를 써보았다

정답코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	// 연산의 개수	// N(1 ≤ N ≤ 100,000)
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		
		for (int n = 0; n < N; n++) {
			int command = Integer.parseInt(br.readLine());
			if (command == 0) {		// 배열에서 가장 작은 수 출력, 제거
				if (heap.isEmpty()) {	// 배열이 비었다면
					System.out.println(0);
				} else {	// 최솟값 출력, 제거
					System.out.println(heap.poll());
				}
			} else {	// 2^31 보다 작은 자연수
				heap.add(command);
			}	
		}
	}
}

성공했다.

이제 BufferedReader를 쓰는 습관을 가져야겠다...