BOJ_S2_15663

📁 [S2_15663] N과 M (9)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_S2_15663 {
	static int N, M;
	static int[] arr;
	static int[] ans;
	static boolean[] check;
	static StringBuilder sb = new StringBuilder();

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

		// **** input start ****

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N];
		ans = new int[M];
		check = new boolean[N];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// **** input end ****

		// 정렬
		Arrays.sort(arr);

		comb(0);

		System.out.println(sb);

	} // main end

	static void comb(int cnt) {
		// 기저조건
		if (cnt == M) {
			for (int i = 0; i < ans.length; i++) {
				sb.append(ans[i]).append(" ");
			}
			sb.append("\n");
			return;
		} else {
			// 이전 값 저장
			int before = 0;
			for (int i = 0; i < N; i++) {
				// 이미 뽑은 것이면
				if (check[i])
					continue;
				// 이전 값과 다르다면
				else if (before != arr[i]) {
					// 방문처리
					check[i] = true;
					// 정답 배열에 값 넣어주기
					ans[cnt] = arr[i];
					// 전의 값 갱신 -> 들어왔던 값이 전의 값으로 된다
					before = arr[i];
					comb(cnt + 1);
					// 백트래킹
					check[i] = false;
				}
			}
		}
	}
} // class end

🤔 나의 생각

이 문제는 combination의 연속 문제들 중 하나이다.
이 문제에서의 조건은 조합에서 전에 값이 나온다면 출력하지 않는 것이다.
그래서 comb 메서드에서 이전 값을 저장해서 만약 이미 뽑은 것이면 통과하고 이전 값과 다르다면 정답 배열에 값을 넣어주고 값이 M 만큼 다 돌았으면 정답 배열 값을 출력한다.
정답 배열을 초기화 시켜줄 필요는 없는게 계속 값을 덮어쓰기 때문이다.