백준 15664 N과 M (10) 자바 풀이

난이도 : 실버2

풀이일 : 2403074

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

15664번: N과 M (10)

---

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

---

풀이 코드

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;
	static int[] result;
	static boolean visited[];
	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];
		visited = new boolean[N];
		set = new LinkedHashSet<>();
		
		for (int i = 0; i < N; i++) {
			nums[i] = sc.nextInt();
		}
		
		Arrays.sort(nums);
		DFS(0, 0);
		
		set.forEach(s -> System.out.println(s));
	}
	
	static void DFS(int depth, int now) {
		if (depth == M) {
			String temp = "";
			for (int i : result) {
				temp += i + " ";
			}
			set.add(temp);
			return;
		}
		for (int i = now; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[depth] = nums[i];
				DFS(depth + 1, i);
				visited[i] = false;
			}
		}
	}
}

• 중복된 수열 출력을 방지하기 위해 set 사용.
• 순서대로 출력을 하기 위해 LinkedHashSet으로 set 구현
• 출력되는 수열이 비내림차순이도록 하기 위해, DFS의 두 번째 인자 now 추가
• 현재 인덱스 이후 인덱스에 대해 visited 확인 후 재귀 호출

---

느낀점

• HashSet과 LinkedHashSet에 대해서도 정리해봐야지.
• 이제 N과 M을 풀 수 있는 날도 얼마 남지 않았다. 부지런히 새 알고리즘을 풀자. 취업이랑 병행하는 친구들은 대체 어떻게 하는거지