순열 구하기

설명

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

 

입력

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

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

 

출력

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

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

 

예시 입력 1 

3 2
3 6 9

 

예시 출력 1

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

 

 

문제 해결

 

static int N, M;
static int[] arr;
static int[] selected;
static boolean[] visited;
static String result = "";

• 숫자의 개수 N, 순열을 만들 때 선택할 숫자의 수 M
• 입력으로 주어지는 자연수를 저장하는 arr 배열
• 선택된 숫자를 저장하는 데 사용하는 selected 배열
• 해당 숫자가 이미 선택되었는지 여부를 나타내는 visited 배열
• 최종 결과 문자열을 저장하는 result 을 전역변수로 선언해준다.

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    M = in.nextInt();

    arr = new int[N];
    selected = new int[M];
    visited = new boolean[N];


    for(int i = 0; i < N; i++) {
        arr[i] = in.nextInt();
    }

    DFS(0);
    System.out.println(result);
}

• main에서는 N, M을 입력받고 arr 배열을 초기화 해주고 DFS(0)를 호출한다.

 

public static void DFS(int L) {
    if (L == M) { // M개를 다 뽑았으면
        for (int num : selected) { //선택된 배열에서 하나씩 뽑아 출력
            result += num + " ";
        }
        result += "\n";
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) { //i번째가 아직 방문되지 않았으면
            visited[i] = true;
            selected[L] = arr[i]; // 현재 선택된 배열의 깊이에 arr i번째 요소 넣기
            DFS(L + 1); //다음 요소 선택
            visited[i] = false; //방문 상태 다시 false로
        }
    }
}

• L이 M과 같아지면, 즉 M개를 다 뽑았으면, 지금까지 선택된 숫자들을 result 문자열에 추가해 출력한다.
• 아직 선택되지 않은 수가 있으면 이를 선택하고 visited 여부를 true로 바꾼 후 현대 선택된 배열의 레벨에 arr배열의 i번째를 추가한 후 다음 레벨로 넘어간다.
• 그리고 이 때 다시 방문상태를 false로 바꿔주어야 한다.

 

 

최종 코드

 

import java.util.Scanner;

public class P06_순열구하기 {
    static int N, M;
    static int[] arr;
    static int[] selected;
    static boolean[] visited;
    static String result = "";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        arr = new int[N];
        selected = new int[M];
        visited = new boolean[N];


        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }

        DFS(0);
        System.out.println(result);
    }

    public static void DFS(int L) {
        if (L == M) { // M개를 다 뽑았으면
            for (int num : selected) { //선택된 배열에서 하나씩 뽑아 출력
                result += num + " ";
            }
            result += "\n";
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) { //i번째가 아직 방문되지 않았으면
                visited[i] = true;
                selected[L] = arr[i]; // 현재 선택된 배열의 깊이에 arr i번째 요소 넣기
                DFS(L + 1); //다음 요소 선택
                visited[i] = false; //방문 상태 다시 false로
            }
        }
    }
}