[백준] 15649 N과 M - 자바

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

문제 풀이

백트래킹 문제로 재귀적으로 풀 수 있다. 

먼저 숫자 범위 n에 대하여 범위에 해당하는 문자열을 만든다. ex) n=4 ➔ 1234, n=7 ➔ 1234567

저 값을 기준으로 하나씩 떼어내서 문자열을 새로 만든다.

이때 종료 조건은 새로 만들어지는 문자열의 갯수가 입력으로 받는 M, 즉 반환해야 하는 문자열의 개수일 것이다.

 

사실 글로만 보면 이해하기 힘들 테니 바로 코드를 보자

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b15649 {
    static StringBuilder sb = new StringBuilder();
    static int k;
    static StringBuilder nums = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++) {
            nums.append(i);
        }
        dfs("", nums.toString());

        System.out.println(sb.toString());
    }

    static void dfs(String now, String remain) {
        if (now.length()==k) sb.append(String.join(" ", now.split("")) + "\n");

        for (int i = 0; i < remain.length(); i++) {
            dfs(now + remain.charAt(i), remain.substring(0, i) + remain.substring(i + 1));
        }
    }
}

당연 핵심 코드는 하나씩 떼어냈을 때 남은 문자열을 재조합하는 부분이다.

dfs(now + remain.charAt(i), remain.substring(0, i) + remain.substring(i + 1));

그림으로 보면 다음처럼 나온다.

느낀점

전에 비슷한 문제를 풀어봐서 바로 접근법을 알고 있었으나 직접 풀어본 건 처음이었다.

막상 알고리즘을 알고나니 크게 어려운 문제는 아니지만 접근법을 모른다면 한참 헤맬 문제인 것 같다.