[Silver 3] [Java] 모든 순열 (10974번)

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

문제 풀이

 

Java Code

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

public class Main {
    static int N;
    static int[] permutation;
    static boolean[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        permutation = new int[N + 1];
        check = new boolean[N + 1];

        getPermutation(1);
    }

    private static void getPermutation(int depth) {
        if (depth == N + 1) {
            getPrintAnswer();
            return;
        }

        for (int index = 1; index <= N; index++) {
            if (!check[index]) {
                check[index] = true;
                permutation[depth] = index;
                getPermutation(depth + 1);
                check[index] = false;
            }
        }
    }

    private static void getPrintAnswer() {
        for (int index = 1; index <= N; index++) {
            System.out.print(permutation[index] + " ");
        }
        System.out.println();
    }
}​