BOJ_S2_15666

📁 [S2_15666] N과 M (12)

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

public class Main {
	static int N, M;
	static int[] arr;
	static int[] res;
	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];
		res = new int[M];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {

			arr[i] = Integer.parseInt(st.nextToken());
		}
		// **** input end ****

		// 정렬
		Arrays.sort(arr);

		dfs(0, 0);

		// 출력
		System.out.println(sb);
	}

	// comb
	static void dfs(int start, int idx) {
		// 기저조건
		if (idx == M) {
			// 결과값들 출력
			for (int i = 0; i < M; i++) {
				sb.append(res[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		// 이전 값 확인 용도
		int num = 0;
		for (int i = start; i < N; i++) {
			// 그전 값이랑 같다면
			if (arr[i] == num)
				continue;

			// 결과 배열에 넣기
			res[idx] = arr[i];
			dfs(i, idx + 1);
			num = arr[i];
		}

	}
}

🤔 나의 생각

이 문제는 N과 M 시리즈 중 한개 ..
dfs로 풀어주었다. 방문체크를 하기 보단 이미 사용했던 것도 사용할 수 있어서 그전 값과 같은지만 판단해서 같으면 통과하고 같지 않다면 결과 배열에 넣어 출력하는 방식으로 구현하였다.
풀이 과정이다.

• N과 M 입력 받기, 배열에 값들 입력
• dfs 메서드를 실행한다.
  • 매개변수 start는 값이 전체 값들을 돌기 시작하는 시작값을 의미
  • 매개변수 idx는 몇 개의 값을 추출했는지 확인
• num이라는 변수로 이전 값이 어떤 값인지 확인해 준다.
• 만약 이전 값이랑 현재 값이랑 같다면 통과
• 다르다면 결과 배열에 값을 넣어준다. 그리고 다시 dfs 메서드를 idx를 하나 증가시킨 상태로 실행한다.
• 만약 idx 가 M이 된다면 ( 과정이 끝난다면 ) 결과 배열을 출력해준다.
• 백트래킹을 통해 num의 값을 이전 값으로 갱신시켜준다.