[백준 / Java] 15650번 N과 M (2)

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 15650번 N과 M (2)

✔ 문제 설명

🚩 요구사항 분석

• 탐색 과정에서 값을 담을 int 배열 생성
• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

🔑 문제풀이

자연수 N과 M을 정의하기 위해 BufferedReader을 사용하여 StringTokenizer로 값을 전역변수 지정하였다.

 

N과 M (1)의 경우처럼 depth를 통해 재귀가 깊어질 때마다 (DMBackTracking함수) depth를 1씩 증가시키는 것은 같다.

 

하지만 고려해야할 사항은 중복되는 수열이 아니며 오름차순 이어야 한다.

그렇다면 현재 값을 확인해 줄 변수가 필요할 것이다.

현재 값보다 다음 재귀가 커야 다음 큰 수를 확인할 수 있기에 i+1로 증가시키며 탐색하였다.

재귀현재위치를 arr배열에 담으며 depth가 M과 같아지면 StringBuilder에 append() 하여 출력하였다.

 

여기서 StringBuilder와 StringBuffer를 활용하는 이유는 문자열 효율성을 위함이다.

https://cobi-98.tistory.com/2

[Java] StringBuffer, StringBuilder

 

 

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

public class Main {

    public static int N;
    public static int M;
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];

        NMBacktracking2(1, 0);
        System.out.println(sb);
    }

    public static void NMBacktracking2(int numberCheck, int depth) {
        if (depth == M) {
            for (int value : arr) {
                sb.append(value).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = numberCheck; i <= N; i++) {
            arr[depth] = i;
            NMBacktracking2(i + 1, depth + 1);
        }
    }
}