Calm Dawn Studio

[JAVA] 백준 15654번 - N과 M (5)

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

public class Main {
	static BufferedReader br;

	static int N; // 1 ~ N 수열의 범위
	static int M; // 고를 수열의 개수
	static int[] numbersN;
	static int[] arr; // 수열을 저장할 배열
	static boolean[] isUsed;
	static StringBuilder sb;

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

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		numbersN = new int[N];
		arr = new int[M];
		isUsed = new boolean[N];
		sb = new StringBuilder();

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			numbersN[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(numbersN); // 오름차순 정렬

		int depth = 0; // 현재 수열의 길이

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

	private static void solution(int depth) throws IOException {

		if (depth == M) {
			for (int num : arr) {
				sb.append(num).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 0; i < N; i++) {
			if (isUsed[i] == false) {
				isUsed[i] = true;
				arr[depth] = numbersN[i];
				solution(depth + 1);
				isUsed[i] = false;
			}
		}
	}
}

백준 백트래킹 문제

정답을 맞춘 풀이방법

1. 이전 N과 M 백트래킹 문제들과 다르게 사용할 N값을 따로 입력받음

2. numbersN[]로 값을 입력받고 오름차순으로 정렬함

3. isUsed를 통해 사용된 숫자인지 체크하고 StringBuilder를 통해 정답 출력함