백준/15649 N과 M(1) // 순열

N과 M (1) 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

72866

45638

30107

61.833%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

---

풀이

예제를 보니 순열의 결과와 같아 보여 순열을 이용하였다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    /**
     * 예제를 보면 순열의 에제와 같다는것을 알 수 있다.
     * 순열은 조합과 다르게 반복문 시작인덱스를 매개변수로 보내지않아도되고, 0으로 반복문을 시작하면 된다 (반복문 시작 인덱스가 0 이라는것은 ,순서가 다르게도 뽑겠다는뜻)
     * 조합과 다르게 visited 방문배열로 뽑은값을 출력하면 안된다 -> 1과 2가 visited에서 true라고 했어도 이게 (1,2)도 이렇게 나타나고 (2,1)도 이렇게 표현되므로
     * 즉 visited 배열 반복문 순회로 뽑힌것을 출력하면 (1,2)와 (2,1)이 구분이 안되기 때문이다.
     *
     * 순열이 동작할때 필요한 매개변수들 -> int n, int r, 뽑을 리스트, 중복방지 방문배열, 뽑은결과 저장할배열, 결과저장할때 인덱스로 쓰고 다 뽑았는지 체크하기위한 depth변수
     * 즉 int n, int r, int[] arr ,boolean[] visited,int[] result , int depth 정도이다.
     * 여기서 int n , int r, int[] arr, boolean[] visited 정도는 static 전역변수로 빼놔도 된다.
     */
    static boolean[] visited;
    static int[] result;
    static int n;
    static int r;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        r = Integer.parseInt(input[1]);
        visited = new boolean[n];
        result = new int[r];

        permutation(result,0);

        bw.flush();
        bw.close();

    }

    public static void permutation(int[] result,int depth) throws IOException{
        if (depth == r) {
            for (int i = 0; i < r; i++) { //뽑은것들 출력
                bw.write(result[i]+" ");
            }
            bw.newLine();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true; //방문배열 뽑았다고 체크
                result[depth]= i+1; //결과 저장에 해당 값 저장
                permutation(result,depth+1); //depth 증가시키며 재귀실행
                visited[i] = false; // 방문배열 안뽑았다고 수정 , result는 알아서 값이 덮어쓰여진다.
            }
        }

    }


}