(Java) 백준 15652 - N과 M (4)

문제 분류가 백트래킹으로 되어 있지만 그냥 재귀를 생각하면서 풀었다.

재귀 탈출문이 실행되고 리턴되면 idx++로 증가시켜 조건에 맞게 문자열을 만들었는데

이걸 백트래킹이라고 볼 수 있는지는 잘 모르겠다...

 

로직

스트림을 사용하기 위해서 입력을 int 배열을 이용해서 받았는데 ,

사실 n, m 변수 하나씩 만들어서 받는 게 편할 수도 있다.

n과 m을 받았다면 재귀 함수를 호출해서 문자열 조합을 만든다.

재귀 호출마다 depth를 증가시키고 depth가 m과 같으면 substring을 사용해서 문자열 앞 공백을 제거하고

문자열을 stringBuilder에 추가하고 리턴한다.

문제 조건에 맞추기 위해서 리턴후에는 idx를 증가시키고 모든 조합이 나올 때까지 재귀 호출을 반복하면 된다.

 

최종 코드

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

public class Main {
    static StringBuilder stringBuilder;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        stringBuilder = new StringBuilder();
        int[] input = Arrays.stream(bufferedReader.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        recursion(input[0], input[1], 0, 1, "");

        System.out.println(stringBuilder);
    }

    static void recursion(int n, int m, int depth, int idx, String str) {
        if (depth == m) {
            str = str.substring(1);
            stringBuilder.append(str).append("\n");
            return;
        }

        for (int i = idx; i <= n; i++) {
            recursion(n, m, depth + 1, idx, str + " " + i);
            idx++;
        }
    }
}