# BOJ15655 N과 M (6)
https://www.acmicpc.net/problem/15655 (opens new window)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구한다. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
# 고려해야 할 점
- N개의 자연수 중에서 M개를 골라야 한다.
- 선택한 자연수는 중복되지 않는다.
- 고른 수열은 오름차순이어야 한다.
- 모두 다른 N개의 자연수가 주어진다. 제공된 자연수는 정렬되어 있지 않다.
# 중복 없이 선택
방문 여부를 가지고 있는 boolean 배열을 활용한다. 주어진 N개의 자연수에서 M개를 고르는 것이기 때문에 모든 배열을 탐색하며 방문 기록만 확인한다.
# 정렬
제공된 자연수는 정렬되어 있지 않다. 사전 순으로 증가하는 순서로 출력하기 위해서 입력된 자연수를 정렬하여 오름차순으로 만든다.
numbers.sort(Comparator.naturalOrder());
# 고른 수열은 오름차순이어야 한다.
고른 수열이 오름차순이기 위해서는 정렬된 자연수를 탐색할 때 처음부터 하는 것이 아니라 현재 시점부터 탐색을 진행해야 한다. 이것을 구현하기 위해 start 변수를 추가적으로 사용한다.
# 제출 코드
아래는 최종 제출 코드이다.
public class BOJ15655 {
private static int n;
private static int m;
private static boolean[] visited;
private static List<Integer> numbers;
private static List<String> results;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
visited = new boolean[n];
numbers = new ArrayList<>();
results = new ArrayList<>();
for (int i = 0; i < n; i++) {
numbers.add(scanner.nextInt());
}
numbers.sort(Comparator.naturalOrder());
backtracking(0, 0, new int[m]);
results.forEach(System.out::println);
}
private static void backtracking(int depth, int start, int[] values) {
if (depth == m) {
String result = Arrays.stream(values)
.mapToObj(String::valueOf)
.collect(joining(" "));
results.add(result);
return;
}
for (int i = start; i < n; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
values[depth] = numbers.get(i);
backtracking(depth + 1, i, values);
visited[i] = false;
}
}
}