Calm Dawn Studio

[JAVA] 백준 12655번 - N과 M (6)

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) {

				if (depth == 0 || (depth > 0 && arr[depth - 1] < numbersN[i])) {
					isUsed[i] = true;
					arr[depth] = numbersN[i];
					solution(depth + 1);
					isUsed[i] = false;
				}

			}
		}
	}
}

백준 백트래킹 문제

정답을 맞춘 풀이방법

1. 기존의 N과 M 유형과 거의 유사함

2. 중복되는 수가 오는 경우르 배제하기 위해서 if(depth ==0 || .... )문으로 분기처리함