BOJ 15654 - N과 M (6)

https://www.acmicpc.net/problem/15655

15655번: N과 M (6)

1. 아이디어

N개의 자연수 중에서 중복 없이 M개를 순서있게 나열하는 완전탐색의 순열문제이다.

 

각 자리에서 재귀호출로 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다. 

 

단, 중복을 허용해야 하고, 오름차순이어야 하므로 재귀함수에 prev인자를 넘겨줘서 다음 자리는 prev+1부터 탐색하게 하여 오름차순이 되도록 설계한다.

N개의 자연수는 모두 다른 수이므로 prev인자를 통해 중복도 방지할 수 있다.

 

2. 시간 복잡도

출처 : https://github.com/rhs0266/FastCampus/

N개의 자연수 중에서 중복 없이 M개를 순서있게 나열하는 순열이므로 시간 복잡도는 O(nPm)이다.

 

N과 M의 최댓값은 8이므로 8! < 1초라서 가능한 접근방법이다.

 

3. 구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] nums, selected;

    public static void main(String[] args) throws IOException {
        input();

        Arrays.sort(nums);

        rec_func(1, 0);

        bw.close();
    }

    static void rec_func(int k, int prev) throws IOException {
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) {
                bw.write(selected[i] + " ");
            }
            bw.write("\n");
        } else {
            for (int i = prev + 1; i <= N; i++) {
                int n = nums[i];

                selected[k] = n;

                rec_func(k + 1, i);

                selected[k] = 0;
            }
        }
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        nums = new int[N + 1];
        selected = new int[M + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }
}