[백준] 15664번 : N과 M (10)

문제

 

 

접근 방식

수열 [1, 7]과 수열 [7, 1]을 같은 경우로 취급하여

오름차순으로 출력하기 위해 [1, 7]만 출력해야 한다.

 

그러면 [1, 7, 8, 9, 9] 라는 배열이 주어졌을 때

1로 시작하는 경우의 수가 7로 시작하는 경우보다 많을 것이고

8보다는 7이, 9보다는 8이 경우의 수가 더 많아지는

시작에서 끝으로 갈수록 경우의 수가 적어지는 규칙이 있다.

 

즉 정렬된 배열에서 이미 사용한 인덱스는 다시 사용할 필요가 없기 때문에

재귀 메서드의 파라미터로 인덱스를 추가로 전달해준다.

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];

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

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

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int seq : sequence) {
				sb.append(seq).append(" ");
			}
			sb.append("\n");
			return;
		}

		int before = 0;

		for (int i = start; i < n; i++) {
			if (before != arr[i]) {
				sequence[size] = arr[i];
				before = arr[i];
				createSequence(size + 1, i + 1);
			}
		}
	}
}