[BOJ] 15649 - N과 M (1) JAVA

www.acmicpc.net/problem/15649

15649번: N과 M (1)

1~N 의 자연수를 사용 하여 나타낼 수 있는 중복되지 않는 M자리 수열을 모두 출력해야한다.

수열들의 순서는 사전 순 오름차순으로 한다.

 

 

 

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static boolean[] check = null;

    // 한자리씩 사용하기 쉽도록 comb, numbers는 String으로 나타냈다
    public static void dfs(int dept, int deptNow, String comb, String numbers) {
        if(dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for(int i = 0; i < numbers.length(); i++) {
            if(check[i] == false) {
                String temp = comb;
                comb += numbers.charAt(i) + " ";  // 출력 주의. 숫자 사이에 공백 넣어야 함
                check[i] = true;

                dfs(dept, deptNow + 1, comb, numbers);

                // 백트래킹
                check[i] = false;
                comb = temp;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        check = new boolean[n];

        String numbers = "";
        for(int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for(int i = 0; i < n; i++) {
            char ch = numbers.charAt(i);
            String comb = String.valueOf(ch) + " ";

            check[i] = true;
            dfs(m, 1, comb, numbers);

            // 백트래킹
            check[i] = false;
        }
    }
}

 

프로그래머스만 풀다가 백준을 풀려니 입출력이 매우 거슬렸다.

 

문제는 전형적인 백트래킹 문제이다.

 

숫자들을 한자리씩 사용하기 쉽도록 String 형태로 넘겨줬다.

 

처음엔 완성된 수열들을 배열에 담아서 정렬을 해야겠다고 생각했는데 생각해보니 어차피 순서대로 만들어지기 때문에 굳이 정렬할 필요도 없었고, 배열에 담을 필요 없이 완성되는 순간 바로 출력하도록 했다.