[문제] 백준 15654번 N과 M (5) - Java

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

기본적인 순열 문제이다.

주의할 점은 수열을 사전순으로 출력해야 한다는 것이다.

그러므로 애초에 입력받은 배열을 오름차순으로 정렬해주는 단계가 필요하다.

 

public class Main {
	static int N,M;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		st = new StringTokenizer(in.readLine(), " ");
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} // 배열 초기화
		
		// 수열은 사전순으로 증가해야하므로 배열을 초기에 오름차순으로 정렬
		Arrays.sort(arr);
		
		// 중복 x , 순열
		perm(0, new int[M], new boolean[N]);
		System.out.print(sb);
	}
	static void perm(int cnt, int[] selected, boolean[] visited) {
		if(cnt == M) {
			for(int i=0;i<cnt;i++) {
				sb.append(selected[i]).append(' ');
			}
			sb.append('\n');
			return;
		} // 기저조건
		
		for(int i=0;i<N;i++) {
			if(!visited[i]) {
				selected[cnt] = arr[i]; 
				visited[i] = true;
				perm(cnt+1, selected, visited);
				visited[i] = false;
			}
		}
	}
	
}