BOJ15656 N과 M (7)

https://www.acmicpc.net/problem/15656 (opens new window)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구한다. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

고려해야 할 점

• N개의 자연수 중에서 M개를 골라야 한다.
• 선택한 자연수는 중복될 수 있다.
• 모두 다른 N개의 자연수가 주어진다. 제공된 자연수는 정렬되어 있지 않다.

선택한 자연수는 중복될 수 있다.

수열은 중복된 자연수를 포함할 수 있다. 즉 방문 여부를 알 필요 없다.

정렬

제공된 자연수는 정렬되어 있지 않다. 사전 순으로 증가하는 순서로 출력하기 위해서 입력된 자연수를 정렬하여 오름차순으로 만든다.

numbers.sort(Comparator.naturalOrder());

제출 코드

아래는 최종 제출 코드이다.

public class BOJ15656 {
    private static int n;
    private static int m;
    private static List<Integer> numbers;
    private static List<String> results;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        numbers = new ArrayList<>();
        results = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            numbers.add(scanner.nextInt());
        }

        numbers.sort(Comparator.naturalOrder());

        backtracking(0, new int[m]);

        System.out.println(String.join("\n", results));
    }

    private static void backtracking(int depth, int[] values) {
        if (depth == m) {
            String result = Arrays.stream(values)
                .mapToObj(String::valueOf)
                .collect(joining(" "));
            results.add(result);
            return;
        }

        for (int i = 0; i < n; i++) {
            values[depth] = numbers.get(i);
            backtracking(depth + 1, values);
        }
    }
}

#BOJ #백트래킹