[백준 JAVA] 1927번: 최소 힙

 

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

 

이 문제 같은 경우는 따로 설계를 안하고 풀어도 될꺼같아서 일단 먼저 풀어 보았다.

 

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

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

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            int cur = Integer.parseInt(br.readLine());
            if(cur == 0){
                if(pq.isEmpty()){
                    System.out.println(0);
                }else{
                    System.out.println(pq.poll());
                }
            }else{
                pq.offer(cur);
            }
        }

    }
}

 

JAVA에 내장 자료구조인 우선순위 큐를 사용하여 쉽게 풀었는데 시간이 좀 오래 걸렸다.

 

시간을 최적화할 방법이 있을까 싶어 GPT 한테 물어보았다.

 

 한가지 정도 아쉽다는 답변을 해주었는데 System.out.println 같은 경우 매번 호출하면 IO 자체가 느리므로 StringBuilder 를 사용하면 좋을꺼같다는 답변이었다.

 

알고 있는 내용이었지만 근래에 이렇게 많은 출력을 해주는 문제가 없어서 인식하지 못하고 있었다.

 

바꿔서 다시 풀어보았다.

 

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

public class Main {
    public static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            int cur = Integer.parseInt(br.readLine());
            if(cur == 0){
                if(pq.isEmpty()){
                    sb.append(0).append('\n');
                }else{
                    sb.append(pq.poll()).append('\n');
                }
            }else{
                pq.offer(cur);
            }
        }

        System.out.println(sb);

    }
}

 

 

생각보다 시간차이가 많이 나는것을 볼 수 있다.

 

꼭 입출력이 많을때는 StringBuilder를 사용하자.