[Inflearn] 자바 알고리즘 문제풀이 #08-06 6. 순열구하기(DFS)

문제

설명

10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

입력 

첫 번째 줄에는 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어진다.

두 번째 줄에는 N개의 자연수가 오름차순으로 주어집니다.

 

출력 

첫 번째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

예시 입력 1 

3 2
3 6 9

예시 출력 1

3 6
3 9
6 3
6 9
9 3
9 6

 

 

 

내 풀이 = 선생님 풀이

import java.util.*;

public class Main8_6 {
    static int n, m;
    static int[] num, answer, ch;
    public void DFS(int L){
        if(L==m) {
            for(int x : answer)
                System.out.print(x + " ");
            System.out.println();
        }
        else {
            for (int i = 0; i < n; i++) {
                if(ch[i]==0){
                    ch[i]=1;
                    answer[L]=num[i];
                    DFS(L+1);
                    ch[i]=0;
                }
            }
        }
    }

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

숫자가 중복이 없어야 한다 = 새 배열(check)을 만들어 사용된 수는 1, 사용이 끝난 수는 0으로 만들어 중복 없이 값이 들어가게 한다.

 

 

 

결과