728x90
난이도 : 실버2
풀이일 : 2403074
https://www.acmicpc.net/problem/15664
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
풀이 코드
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을 풀 수 있는 날도 얼마 남지 않았다. 부지런히 새 알고리즘을 풀자. 취업이랑 병행하는 친구들은 대체 어떻게 하는거지
'알고리즘 > 🥈 실버' 카테고리의 다른 글
백준 10815 숫자 카드 자바스크립트 풀이 (0) | 2024.03.16 |
---|---|
백준 15665 N과 M(11) 자바 풀이 (0) | 2024.03.13 |
백준 15663 N과 M (9) 자바 풀이 (0) | 2024.03.03 |
백준 15657 N과 M (8) 자바 풀이 (0) | 2024.03.02 |
백준 15656 N과 M (7) 자바 풀이 (0) | 2024.02.29 |