4. 중복 순열

1. 문제

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

 

자연수 N과 M이 주어진다. (3 <= N <= 10), (2 <= M <= n)

 

입력 예시 1

3 2

 

출력 예시 1

1 1

 

 

2 - 1. 나의 풀이

맨 처음 풀 때는 매우 어렵게 풀었다.

 

String에 1~n까지 옆으로 붙인 다음

DFS를 호출

DFS호출이 끝나면 그전에 저장해둔 tmp으로 롤백

 

지금 보면 어떻게 이런 생각으로 풀었나 싶음

강의를 수강하고 1주뒤에 다시 풀었다.

 

2 - 2. 나의 코드

package DFS_BFS_levelup;
import java.util.Scanner;

public class dfs_04_myself {
    public static int n;
    public static int m; //m단계 까지만
    public static String answer = "";

    //L은 단계 (m까지)
    public static void DFS(int L) {
        if(L == m){
            System.out.println(answer);
        }else{
            for (int i = 1; i <= n; i++) {
                String tmp = answer;
                answer = answer + i + " ";
                DFS(L + 1);
                answer = tmp;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();


        DFS(0);



    }
}

 

 

3 - 1. 강의 풀이

계층 L이 m까지 증가하며 DFS 재귀를 호출하는 건 같음

하지만 더 직관적으로 보기 쉽게 풀었다.

 

크기가 m인 int 배열(pm or arr)을 설정하고

pm[L] = i; 후 재귀 호출

 

3 - 2. 강의 코드

package DFS_BFS_levelup;
import java.util.*;

public class pratice_myself {
    public static int n,m;
    public static int[] arr;

    public static void DFS(int L) {
        if (L == m) {
            for(int x : arr) System.out.print(x + " ");
            System.out.println();
        }else {
            for (int i = 1; i <= n; i++) {
                arr[L] = i;
                DFS(L + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m];
        DFS(0);

    }
}

 

4. 얻어갈 점

복습의 중요성