백준 15655 N과 M (6) 자바 풀이

난이도 : 실버3

풀이일 : 2402014

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

15655번: N과 M (6)

---

링크로 이동하기 귀찮은 분들을 위한 문제캡쳐

---

풀이 코드

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	static int N, M;
	static int[] nums;
	static int[] result;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		nums = new int[N];
		visited = new boolean[N];
		result = new int[M];
		
		
		for (int i = 0; i < N; i++) {
			nums[i] = sc.nextInt();
		}
		
		Arrays.sort(nums);
		
		DFS(0, 0);
		System.out.println(sb);
	}
	
	static void DFS(int depth, int n) {
		if (depth == M) {
			for (int i : result) {
				sb.append(i + " ");
			}
			sb.append('\n');
			return;
		}
		for (int i = n; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[depth] = nums[i];
				DFS(depth + 1, i);
				visited[i] = false;
			}
		}
	}
}

• 중복 숫자 출력 방지를 위한 visited 배열 생성
• 오름 차순으로만 숫자를 출력하기 위해 DFS에 현재 숫자를 함께 인자로 전달

---

느낀점

• 파이썬 골드 문제를 풀다 실패해서 오늘도 좋게 말하면 유형 뽀개기, 나쁘게 말하면 날먹 느낌으로 N과 M 문제 풀이