[JAVA] 백준 15657번

[JAVA] 백준 15657번 - N과 M (8)

 

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 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];
		sb = new StringBuilder();

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

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

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

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

		solution(startSearchIdx, depth);
		System.out.print(sb.toString());
	}

	private static void solution(int startSearchIdx, int depth) throws IOException {

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

		for (int i = startSearchIdx; i < N; i++) {
			arr[depth] = numbersN[i];
			solution(i, depth + 1);
		}
	}
}

백준 백트래킹 문제

 

정답을 맞춘 풀이방법

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

2. 현재 수열의 위치부터 탐색을 시작해야 하기 때문에 startSearchIdx 값 추가함

3. StringBuilder를 이용해 정답출력