문제

지정된 수의 수열을 출력하세요.

코드

public class Permutation {
    static int m,n = 0;
    static int[] ch;
    static int[] pm;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        int[] arr = new int[m];
        ch = new int[m];
        pm = new int[n];
        for(int i=0; i<m; i++){
            arr[i] = sc.nextInt();
        }

        solution(arr);
    }
    public static void solution(int[] arr){
        dfs(0, arr);
    }
    public static void dfs(int level, int[] arr){
        if(level == n){
            for(int i : pm){
                System.out.print(i+" ");
            }
            System.out.println();
        }else{
            for(int i=0; i<m; i++){
                if(ch[i] != 1){
                    pm[level] = arr[i];
                    ch[i] = 1;
                    dfs(level+1, arr);
                    ch[i] = 0;
                }
            }
        }
    }
}

설명

dfs 알고리즘을 사용하여 순열을 구하는 문제이다. 저번 문제랑 다른점은 중복을 허용하지 않는다는 것인데. 그래서 ch[] 배열을 추가하여 체크가 된 수들은 출력하지 않도록 작성하여 중복을 허용하지 않는 방법을 채택하였다.

dfs 내의 알고리즘 로직은 첫 if문에서 n까지 진행할 수 있도록 하였고 n이 되었을 때 pm[] 안에 숫자를 출력하는 방식으로 진행하였다.

n이 아닐 경우에는 pm[] 배열에 우리가 원하는 값이 들어있지 않으므로 ch[] 배열을 먼저 체크 후 pm[] 배열의 값을 넣어준다. 그리고 ch[] 배열의 값을 1으로 변경하여 로직내 dfs() 재귀 호출이 실행되었을 때 중복값을 제외할 수 있도록 한다. 그리고 dfs()를 반환 받으면 다시 ch[]의 값을 0으로 변경하여 다음 for문의 실행에서는 다시 값을 체크할 수 있도록 한다.

이렇게 간단하게 설명하는 이유는 그동안 문제를 단계별로 풀어왔다면 다 이해할 수 있는 수준이여서 그렇다.

강의를 듣기전 먼저 풀어봤는데 생각보다 쉽게 풀려서 놀랐다. 점점 dfs 문제에 익숙해져가는 것 같은데 문제를 이렇게 직설적으로 간단하게 내지 않으니 그때 내가 아직 풀수 있을지 모르겠다ㅜㅜ 더 연습하자!