백준 15665 N과 M(11) 자바 풀이

난이도 : 실버2

풀이일 : 2403096

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

15665번: N과 M (11)

---

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

---

풀이 코드

import java.util.Scanner;
import java.util.Arrays;
import java.util.Set;
import java.util.LinkedHashSet;


public class Main {
	static int N, M;
	static int[] nums, result;
	static Set<String> set;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		nums = new int[N];
		result = new int[M];
		set = new LinkedHashSet<>();
		
		for (int i = 0; i < N; i++) {
			nums[i] = sc.nextInt();
		}
		
		Arrays.sort(nums);
		DFS(0);
		
		set.forEach(s -> System.out.println(s));
	}
	static void DFS(int depth) {
		if (depth == M) {
			String temp = "";
			for (int i : result) {
				temp += i + " ";
			}
			set.add(temp);
			return;
		}
		for (int i = 0; i < N; i++) {
			result[depth] = nums[i];
			DFS(depth + 1);
		}
	}
}

• 같은 수를 여러번 출력해도 되므로 visited 배열 불필요
• 현재 수보다 작은 수를 출력해도 되므로 DFS 속 반복문은 0부터 시작
• nums : 주어진 N개의 수를 저장할 배열
• result : M개의 수를 저장할 배열
• set : 중복 값 없이 숫자들을 담기 위해 set, 순서대로 출력하기 위해 LinkedHashSet 사용

---

느낀점

• 이제 N과 M이 한 문제 밖에 남지 않았다. 이런 문제를 한동안 잔뜩 풀어서 이제 비슷한 문제는 틀리지 않을 것 같다. 다음 주제로 넘어가야지