순열 구하기

13 May 2023 in Algorithm on Java, Coding, Test

문제

문제

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.*;

class Main {
    static int[] pm, ch, arr;
    static int n, m;

    public void DFS(int L) {
        // m 개를 뽑은 경우 배열에서 출력
        if (L == m) {
            for (int x : pm) System.out.print(x + " ");
            System.out.println();
        } else {
            // 반복을 통해 재귀호출
            for (int i = 0; i < n; i++) {
                // 뽑지 않은 경우에만 진행
                if (ch[i] == 0) {
                    // 체크 배열에 뽑았다고 체크 후, 
                    ch[i] = 1;
                    // 값을 넣어준 뒤
                    pm[L] = arr[i];
                    // 재귀 호출하고
                    DFS(L + 1);
                    // 다시 뽑지 않음으로 돌림.
                    ch[i] = 0;
                }
            }
        }
    }

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