[백준] 15649번 N과 M (1) 자바 풀이

문제

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

DFS 이용하여 모든 인덱스 순회 함.

코드

import java.util.Scanner;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static StringBuilder result = new StringBuilder();
    public static void dfs(int[] arr, boolean[] visited, int depth, int index, int d) {
        visited[index] = true;
        sb.append(arr[index]+" ");
        if (depth == 1)  {
            result.append(sb + "\n");
            return;
        }
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                dfs(arr, visited, depth-1, i, d);
                visited[i] = false;
                sb.delete(sb.length()-2, sb.length());
            }
        }

    }

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

        int a = sc.nextInt();
        int b = sc.nextInt();

        int[] arr = new int[a];
        boolean[] visited = new boolean[a];
        for (int i = 0; i < a; i++) {
            arr[i] = i+1;
        }

        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                dfs(arr, visited, b, i, b);
                visited[i] = false;
                sb.setLength(0);
            }
        }
        System.out.println(result);
    }
}

StringBuilder 변수를 두개 이용하여 출력을 1회로 수정 후 시간이 1220ms → 268ms 로 많이 줄었다.