아이디어

• 기본적으로 입력을 오름차순 정렬 후 순열을 이용한 브루트포스 문제
• 문제에서 주어진 수는 모든 다른 수라고 보장하였으므로, 중복된 수열이 나오는 일은 절대 없다. 따라서 이에 대해 처리하지 않아도 된다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, M, A[];
	static int[] buf;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		A = new int[N];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++)
			A[i] = Integer.parseInt(tk.nextToken());
		
		Arrays.sort(A);
		
		buf = new int[M];
		
		for (int i=0; i<N; i++)
			perm(i, 0);

		System.out.println(sb);
	}

	static void perm(int idx, int d) {
		buf[d] = A[idx];
		
		if (d == M - 1) {
			for (int i=0; i<M; i++) {
				sb.append(buf[i]).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i=0; i<N; i++) {
			perm(i, d + 1);
		}
		
	}
}

메모리 및 시간

• 메모리: 123196 KB
• 시간: 616 ms

리뷰

• 이전에 푼 'N과 M (12)'에서 비내림차순 조건을 풀면 풀릴 줄 알았는데, 이 조건이 꽤 많은 가지치기를 해준다는 것을 알지 못했었다.