# BOJ15664 N과 M (10)
https://www.acmicpc.net/problem/15664 (opens new window)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구한다. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
# 고려해야 할 점
- N개의 자연수 중에서 M개를 골라야 한다.
- N개의 자연수는 중복된 수를 포함한다.
- 고른 수열은 오름차순이어야 한다.
- 모두 다른 N개의 자연수가 주어진다. 제공된 자연수는 정렬되어 있지 않다.
# 중복 없이 선택
방문 여부를 가지고 있는 boolean 배열을 활용한다. 주어진 N개의 자연수에서 M개를 고르는 것이기 때문에 모든 배열을 탐색하며 방문 기록만 확인한다.
# 정렬
제공된 자연수는 정렬되어 있지 않다. 사전 순으로 증가하는 순서로 출력하기 위해서 입력된 자연수를 정렬하여 오름차순으로 만든다.
numbers.sort(Comparator.naturalOrder());
# 고른 수열은 오름차순이어야 한다.
고른 수열이 오름차순이기 위해서는 정렬된 자연수를 탐색할 때 처음부터 하는 것이 아니라 현재 시점부터 탐색을 진행해야 한다. 이것을 구현하기 위해 start 변수를 추가적으로 사용한다.
# LinkedHashSet
해당 문제의 예제를 살펴보면 주어진 N개의 자연수에 중복된 수가 포함된다. 이것이 의미하는 것은 단순히 숫자를 고를경우 중복되는 수열이 여러 번 출력될 수 있다는 것을 의미한다. 즉 결과값을 유일하게 만들어야 한다.
Set은 수학의 집합처럼 순서와 상관없이 중복을 허용하지 않는다. 여기서 한 가지 주목해야 할 점은 순서를 고려하지 않는다는 것이다. 하지만 Set의 구현체인 LinkedHashSet은 입력된 순서대로 데이터를 관리한다.
정리하면 LinkedHashSet을 사용하면 중복되지 않고 입력된 순서대로 데이터를 관리할 수 있다.
# 제출 코드
아래는 최종 제출 코드이다.
public class BOJ15664 {
private static int n;
private static int m;
private static boolean[] visited;
private static List<Integer> numbers;
private static Set<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 LinkedHashSet<>();
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;
}
}
}