BEAKJOON / 백준 - JAVA 11279번 최대 힙

2024.08.06기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 입력에 0이 들어온다면 가장 큰 값을 출력하고 0이 아닌 수는 큐에 추가해주는 문제입니다.

 

이 문제의 핵심은 시간 초과가 안나는게 핵심이라고 생각합니다.

그러긴 위해서 우선순위 큐(PriorityQueue)를 사용하는 것이 편리합니다.

 

1. 우선순위 큐를 내림차순으로 선언을 해줍니다.

// 큐를 내림차순으로 정렬을 하면서 추가한다.
PriorityQueue<Integer> qu = new PriorityQueue<>(Collections.reverseOrder());

 

2. 0이 들어오면 큐의 가장 앞에 있는 수 또는 0을 다른 수가 들어오면 큐에 추가해줍니다.

while (n-- > 0) {
    num = Integer.parseInt(br.readLine());

    if (num == 0) {
        if (qu.isEmpty()) { // 큐에 아무것도 없다면
            sb.append(0);
        } else { // 큐 맨 앞 수를 출력
            sb.append(qu.poll());
        }

        sb.append("\n");
    } else { // 큐에 수를 추가
        qu.offer(num);
    }
}

 

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 연산의 개수
		
		// 큐를 내림차순으로 정렬을 하면서 추가한다.
		PriorityQueue<Integer> qu = new PriorityQueue<>(Collections.reverseOrder());
		int num;
		
		while (n-- > 0) {
			num = Integer.parseInt(br.readLine());
			
			if (num == 0) {
				if (qu.isEmpty()) { // 큐에 아무것도 없다면
					sb.append(0);
				} else { // 큐 맨 앞 수를 출력
					sb.append(qu.poll());
				}
				
				sb.append("\n");
			} else { // 큐에 수를 추가
				qu.offer(num);
			}
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}