BOJ15657 N과 M (8)

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

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

고려해야 할 점

• N개의 자연수 중 M개를 골라야 한다.
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 모두 다른 N개의 자연수가 주어진다. 제공된 자연수는 정렬되어 있지 않다.

같은 수를 여러 번 골라도 된다.

수열에 선택된 자연수는 중복을 허용한다. 즉 방문 여부를 가지고 있지 않아도 된다.

고른 수열은 비내림차순이어야 한다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이다. 이전에 탐색한 자연수를 포함하여 이후 번호를 탐색하면 비내림차순을 보장한다. 이것을 구현하기 위해 start 변수가 사용된다.

정렬

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

numbers.sort(Comparator.naturalOrder());

제출 코드

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

public class BOJ15657 {
    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, 0, new int[m]);

        results.forEach(System.out::println);
    }

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

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

#BOJ #백트래킹