[ps java] fast I/O 정확하게 알고 쓰기

JAVA 같은 엔터프라이즈 언어의 입출력은 타 언어에 비해서 상대적으로 느리며, 특히 System.out.println()을 여러 번 호출하면 성능에 큰 영향을 미친다. 따라서 우리는 익히 아는 BufferReader와 StringBuilder를 사용하는데, StringBuilder를 ps에서 명확하게 사용하는 방법을 알아보고자 한다.

 

먼저 다음의 코드를 살펴보자! 전형적인 큐의 웰노운 문제이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            
            StringBuilder sb = new StringBuilder();
            if (cmd.equals("push")) {
                queue.offer(Integer.parseInt(st.nextToken()));
            }
            else if (cmd.equals("pop")) {
                if (queue.isEmpty()) {
                    sb.append(-1);
                } else {
                    sb.append(queue.poll());
                }
            }
            else if (cmd.equals("size")) {
                sb.append(queue.size());
            }
            else if (cmd.equals("empty")) {
                if (queue.isEmpty()) {
                    sb.append(1);
                } else {
                    sb.append(0);
                }
            }
            else if (cmd.equals("front")) {
                if (queue.isEmpty()) {
                    sb.append(-1);
                } else {
                    sb.append(queue.peekFirst());
                }
            }
            else if (cmd.equals("back")) {
                if (queue.isEmpty()) {
                    sb.append(-1);
                } else {
                    sb.append(queue.peekLast());
                }
            }
            System.out.println(sb);
        }
        br.close();
    }
}

 

StringBuilder를 사용하며 보기에는 문제가 별 없어 보이지만, 시간 초과가 딱 나기 좋은 코드이다

그 이유는 StringBuilder를 사용하더라도, 매 반복문마다 sout으로 출력을 한다면 명령어의 개수만큼 출력 작업이 발생해 출력 작업이 많아질수록 성능에 큰 영향을 미치기 때문이다

 

 

따라서 위의 코드는 모든 출력 결과를 한 번에 모아서 출력하는 방식으로 변경해야 한다

이를 위해 StringBuilder를 하나만 생성한 후, 명령어 처리 결과를 누적하고, 마지막에 한 번만 출력하도록 수정하면 된다

수정한 코드는 다음과 같다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> queue = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            if (cmd.equals("push")) {
                queue.offer(Integer.parseInt(st.nextToken()));
            }
            else if (cmd.equals("pop")) {
                if (queue.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(queue.poll()).append("\n");
                }
            }
            else if (cmd.equals("size")) {
                sb.append(queue.size()).append("\n");
            }
            else if (cmd.equals("empty")) {
                if (queue.isEmpty()) {
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            }
            else if (cmd.equals("front")) {
                if (queue.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(queue.peekFirst()).append("\n");
                }
            }
            else if (cmd.equals("back")) {
                if (queue.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(queue.peekLast()).append("\n");
                }
            }
        }
        System.out.println(sb);

        br.close();
    }
}

 

1. 반복문 안에서 System.out.println() 호출:

• 출력 작업이 명령의 개수만큼 반복
• 시간 복잡도: O(N)

2. StringBuilder에 누적 후 한 번만 출력:

• 출력 작업은 단 한 번만 수행
• 시간 복잡도: O(1)

 

Java에서 코딩 테스트를 진행할 때, 출력 최적화는 매우 중요한 요소이다. 특히, System.out.println()의 반복 호출은 시간 초과(TLE, Time Limit Exceeded)를 유발할 수 있다. 이번 글에서는 StringBuilder를 사용하여 출력 작업을 최적화하고, 출력 작업을 반복문 안에서 처리했을 때와 한 번에 처리했을 때의 차이를 중점적으로 다뤄봤다.

다시 반복해서 강조하면, Java에서 입력 및 출력이 중요한 코딩 테스트에서 반복적인 출력 작업은 피해야 한다. 대신, StringBuilder를 활용하여 출력 결과를 누적하고, 최종적으로 한 번만 출력하는 방식으로 문제를 해결할 수 있다. 이러한 최적화는 특히 명령어의 개수가 많은 경우, 성능에 큰 차이를 가져온다. 이 글에서 다룬 방식은 큐와 같은 자료구조 문제뿐만 아니라, 대량의 데이터를 다룰 때 항상 적용 가능한 방법이다. "작은 최적화가 큰 성능 차이를 만든다"는 점을 기억하며 코딩에 임하길 바란다!

 

 

 

 

 

 

(문제 링크)

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