[백준알고리즘] 15654 - N과 M (5)

www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

이 문제는 순열을 구현하는 문제입니다. 기존 기본 순열 문제와 다른 점은 출력할 수가 주어진다는 것입니다.

 

n, m, 출력할 숫자 배열(nums)을 입력받고 nums를 오름차순으로 정렬합니다. 그런 다음 순열을 구하는 메소드에 (nums, 실제 선택된 수 배열, nums이 각 인덱스가 선택되었는지 확인할 배열, n, m, 선택된 숫자 개수)를 전달합니다.

 

선택된 숫자 개수(depth)가 m과 같은 경우는 출력을 하고 그렇지 않은 경우 가장 처음 수부터 반복하면서 해당 숫자를 선택했는지 확인합니다. 아직 선택하지 않은 경우 그 수를 선택한 것으로 하고 실제 선택된 수 배열에 추가합니다. 그리고 다시 순열을 구하는 메소드를 재귀 호출합니다. 이때 하나의 수를 선택했기 때문에 depth + 1을 전달합니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(nums);

        permutation(nums, new int[n], new boolean[n], n, m, 0);
    }

    private static void permutation(int[] nums, int[] selected, boolean[] isSelect, int n, int m, int depth) {
        if (depth == m) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < depth; i++) {
                sb.append(selected[i]).append(" ");
            }

            System.out.println(sb);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isSelect[i]) {
                isSelect[i] = true;
                selected[depth] = nums[i];
                permutation(nums, selected, isSelect, n, m, depth + 1);
                isSelect[i] = false;
            }
        }
    }
}