BOJ - 모든 순열

 

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

10974번: 모든 순열

 

• 기본적인 완전 탐색이다.
• 해당 문제를 풀며 실행 속도에 대해 조금 고민을 했었는데 최적화 결과는 사진과 같다.

1. 재귀 함수 파라메터를 전역변수로 옮김 (548 -> 316)
2. StringBuilder.append 함수를 " " -> ' '로 변경 (316->256)
3. Java에서 " "는 String Class 를 생성하는 것 같다.

 

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


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N;
    private static StringBuilder builder = new StringBuilder();
    private static boolean[] visit;
    private static char[] str;

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine());

        visit = new boolean[N + 1];
        str = new char[N];
        dp(0);
        System.out.println(builder);
    }

    private static void dp(int depth) {
        if (depth == N) {
            for (int i = 0; i < str.length; i++) {
                builder.append(str[i]).append(' ');
            }
            builder.append('\n');
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (visit[i]) continue;
            visit[i] = true;
            str[depth] = (char) (i + '0');
            dp(depth + 1);
            visit[i] = false;
        }
    }
}