백준 - 10974번(모든 순열)

문제 출처: https://www.acmicpc.net/problem/10974

문제

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

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

public class Main {

    private static StringBuilder result = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] nums = new int[N]; // 1 2 3
        boolean[] check = new boolean[N]; // false false false
        for (int i = 0; i < N; i++) {
            nums[i] = i + 1;
        }
        permutation(nums, check, N, new StringBuilder());

        System.out.println(result);
    }

    private static void permutation(int[] nums, boolean[] check, int count, StringBuilder sb) {
        if (count == 0) {
            result.append(sb).append("\n");
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!check[i]) {
                check[i] = true; // 1을 뽑음
                sb.append(nums[i]).append(" ");
                permutation(nums, check, count - 1, sb);
                sb.setLength(sb.length() - 2);
                check[i] = false;
            }
        }
    }

}

• 처음에 순열이라는 것만 보고 겁먹고 들어간 문제
• 아직 재귀가 익숙치 않아서 이렇게 저렇게 많은 시도를 하였다.
• 각 숫자마다 뽑았는지를 확인하는 배열을 둬서 그 배열을 통해 뽑을 수 있도록 처리하였다.
• 가장 간단히 숫자가 2까지만 있다고 가정하여 로직을 설계하고, 이를 재귀로 적용하여 전체 수에 적용하였다.
• 항상 index를 처음부터 살피므로 사전순 정렬은 자동적으로 수행되었다.
• 처음에는 N개를 다 찾았을 때 바로 바로 출력을 했는데, 이것보다 StringBuilder를 사용하는 것의 수행 시간이 매우 많이 차이가 났다(960ms -> 176ms).