[알고리즘] 완전 탐색 - 중복 순열 (백준 15651번. N과 M(3) - JAVA)

중복순열

서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수 

(1) 중복을 허용해서 (a) 순서있게 나열하기 

 

중복 순열의 경우의 수

예시

{1,2,3} 중 3개의 원소를 선택한 중복 순열의 결과는 {111,112,113,121,...,333} 총 27가지 나온다. n의 r승계의 경우의 수를 가지므로 3의 3승계 (3*3*3 = 27)이다.

 

 

백준 15651번. N과 M(3)

 

조건 

• 1부터 N까지 자연수 중에서 M개를 고른 수열 ( 순서 있게 나열하기) 
• 같은 수를 여러 번 골라도 된다. (중복 허용) 

 

풀이 방법

1차

• 재귀 사용 (백트래킹) 
• Scanner + System.out.println() → 시간초과 (출력을 반복해서 시간초과가 뜸)

import java.util.Scanner;

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

        for(int i = 0; i<arr.length; i++){
            arr[i] = i+1;
        }
        permutation(arr, new int[M], 0, M);
    }

    private static void permutation(int[] arr, int[] out, int depth, int M) {
       if(depth == M){
           for(int num: out) System.out.print(num + " ");
           System.out.println();
           return;
       }
       for(int i= 0; i<arr.length; i++){
           out[depth] = arr[i];
           permutation(arr, out, depth+1, M);
       }
    }
}

 

2차

• 재귀 사용 (백트래킹) 
• Scanner + StringBuffer → 정답

import java.util.Scanner;

public class Main {
    static int N, M;
    static StringBuffer sb = new StringBuffer();
    static int[] out;

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

        permutation(out,0);
        System.out.println(sb);
    }

    private static void permutation(int[] out ,int depth) {
        if(depth == M){
            for(int num : out) sb.append(num).append(" ");
            sb.append("\n");
            return;
        }

        for(int i = 1; i<=N; i++){
            out[depth] = i;
            permutation(out,depth+1);
        }
    }
}