10974 모든 수열

문제

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

입력

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

출력

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

예제 입력 1

3

예제 출력 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

코드

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

public class P_10974 {
    static int      n;
    static int[]    perm;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());

        init_perm();
        print_perm();
        while (find_next_perm()) {
            print_perm();
        }
        bw.flush();
    }

    public static void init_perm() {
        perm = new int[n];
        for (int i = 1; i<= n; i++) {
            perm[i - 1] = i;
        }
    }

    public static void print_perm() throws IOException {
        for (int num : perm) bw.write(num + " ");
        bw.newLine();
    }

    public static boolean find_next_perm() throws IOException {
        int idx = -1;

        for (int i = n - 2; i>= 0; i--) {
            if (perm[i] < perm[i + 1]) {
                idx = i;
                break;
            }
        }

        if (idx == -1) return false;
        else {
            for (int j = n - 1; j > idx; j--) {
                if (perm[j] > perm[idx]) {
                    int temp = perm[j];
                    perm[j] = perm[idx];
                    perm[idx] = temp;
                    break;
                }
            }
            Arrays.sort(perm, idx + 1, n);
            return true;
        }
    }
}

코드 설명

[P.10972 다음 순열] 방식을 이용했다.