BOJ15651 N과 M (3)

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

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

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

고려해야 할 점

• 1부터 N까지 자연수 중에서 M개를 골라야 한다.
• 같은 수를 여러 번 골라도 된다.

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

정리하면 중복을 허용한다. 방문 기록을 확인할 필요가 없다.

시간 초과

해당 문제는 다른 N과 M문제보다 많은 출력을 가지고 있다. 빈번한 System.out.println() 호출은 동기화 키워드로 인한 많은 시간을 소요하게 된다. 즉 출력을 위한 문자열을 만든 후 한 번에 출력하도록 구현 해야 한다.

개선 전

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

개선 후

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

String.join 메서드의 내부 코드를 살펴보면 StringJoiner를 사용해서 문자열을 연결하고 있다.

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    ...
    public static String join(CharSequence delimiter,
            Iterable<? extends CharSequence> elements) {
        Objects.requireNonNull(delimiter);
        Objects.requireNonNull(elements);
        StringJoiner joiner = new StringJoiner(delimiter);
        for (CharSequence cs: elements) {
            joiner.add(cs);
        }
        return joiner.toString();
    }
    ...
}

제출 코드

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

public class BOJ15651 {
    private static int n;
    private static int m;
    private static List<String> results;

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

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

        results = new ArrayList<>();

        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 = 1; i <= n; i++) {
            values[depth] = i;
            backtracking(depth + 1, values);
        }
    }
}

#BOJ #백트래킹