sout는 느리다. 그러면 stringbuilder를 사용하자.

아니 분명 맞게 풀었는데, 그리고 최적화된 문제풀이라고 자신했는데 계속해서 시간초과가 발생했다. 뭐가 문제일까?

sout는 느리다는 것이다. 그러면 어떻게 대체를 할까?

알고리즘 문제에서 출력 최적화를 위해 BufferedWriter와 StringBuilder를 사용하는 패턴을 사용하는 것이다. 이 방식은 특히 많은 출력을 요구하는 문제에서 System.out.println을 대체하여 효율성을 높여준다.

1. BufferedWriter와 StringBuilder 사용 이유

• 성능 최적화: System.out.println은 출력할 때마다 버퍼에 접근하여 시간이 소요됩니다. BufferedWriter는 내용을 버퍼에 모아두었다가 한 번에 출력하여 실행 시간을 줄입니다.
• StringBuilder의 효율적인 문자열 조작: StringBuilder는 문자열을 효율적으로 연결하며, + 연산을 여러 번 사용하는 것보다 빠릅니다.

2. 알고리즘 문제에서 BufferedWriter와 StringBuilder를 활용하는 기본 패턴

아래는 입력 및 출력 예제 코드입니다. 입력을 받을 때는 BufferedReader를, 출력을 할 때는 BufferedWriter와 StringBuilder를 사용합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Example {
    public static void main(String[] args) throws IOException {
        // 1. BufferedReader로 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 2. BufferedWriter로 출력하기
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 3. StringBuilder 생성
        StringBuilder sb = new StringBuilder();
        
        // 입력 예제
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 예제 작업 (1부터 n까지 숫자 출력 예시)
        for (int i = 1; i <= n; i++) {
            sb.append(i).append(" ");
            if (i % m == 0) sb.append("\n");  // 특정 조건에 따라 줄바꿈 추가
        }

        // 4. BufferedWriter로 StringBuilder의 내용을 한 번에 출력
        bw.write(sb.toString());
        
        // 자원 해제
        bw.flush();
        bw.close();
        br.close();
    }
}

3. BufferedWriter와 StringBuilder 사용 단계별 설명

1. BufferedReader를 이용한 입력:

   • BufferedReader는 Scanner보다 빠른 입력을 처리할 수 있어 큰 입력이 필요한 알고리즘 문제에서 유리합니다.
   • StringTokenizer를 사용해 공백으로 구분된 여러 개의 입력을 쉽게 분리할 수 있습니다.

2. StringBuilder를 사용해 출력 내용 준비:

   • 모든 출력 데이터를 StringBuilder에 append()로 누적하여 저장합니다.
   • 줄바꿈이 필요할 경우 append("\n")을 사용합니다.

3. BufferedWriter를 통해 출력:

   • 모든 작업이 끝난 후 BufferedWriter의 write() 메소드를 통해 StringBuilder의 내용을 한 번에 출력합니다.
   • flush()를 사용하여 남은 버퍼를 강제로 출력하고, close()로 BufferedWriter를 닫아 자원을 해제합니다.

4. 문제 풀이에서 자주 사용하는 패턴들

• 여러 줄 출력: 반복문에서 StringBuilder에 한 번에 내용을 누적시키고, 마지막에 출력하는 방식으로 처리합니다.
• 조건부 출력: StringBuilder에 if문을 사용하여 특정 조건에서만 append("\n")을 추가하는 방식으로 줄바꿈을 조정할 수 있습니다.
• DFS, BFS와 같은 재귀 호출이 많은 경우: 출력할 내용을 재귀 호출 중에 StringBuilder에 저장하고, 모든 재귀가 끝난 후에 한 번에 출력합니다.

5. 실전에서의 예제 코드 - 재귀적 DFS 예제

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class DFSExample {
    private static int n, m;
    private static StringBuilder result = new StringBuilder();

    private static void dfs(int depth, int[] temp) {
        if (depth == m) {
            for (int i = 1; i <= m; i++) {
                result.append(temp[i]).append(" ");
            }
            result.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            temp[depth + 1] = i;
            dfs(depth + 1, temp);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);

        int[] temp = new int[m + 1];
        dfs(0, temp);

        bw.write(result.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

이 패턴을 익히면 출력 속도가 중요한 문제에서 성능 향상을 경험할 수 있습니다. BufferedWriter와 StringBuilder를 잘 활용하면 대량의 출력 작업에서 특히 유리하니, 앞으로 알고리즘 문제를 풀 때 활용해 보세요!

앞으로 이런 식으로 문제를 풀어야겠다. 근데 어려워 ㅠㅠ