첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
이전의 N과M 문제들과 다른 점은 중복된 수가 존재한다는 점
중복되는 수열을 여러번 출력하면 안된다는 조건때문에 확인해야한다.
이 부분을 dfs
함수의 조건문으로 걸어줬는데,
이 전의 숫자를 before
라는 변수로 저장해두고
새로 입력된 숫자와 비교해서 같으면 출력하지 않고
다르면 출력하는 방식의 조건문이다.
처음엔 set
을 이용해 중복된 수를 제거해야하는 줄 알았는데
다시 읽어보니 그게 아니었다!
문제 똑바로 읽어야한다..
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] result, arr;
static boolean [] visited;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
result = new int[M];
visited = new boolean[N];
arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
dfs(0);
System.out.println(sb);
}
static void dfs(int cnt) {
if (cnt == M) {
for (int i : result) {
sb.append(i).append(" ");
}
sb.append("\n");
return;
}
int before = 0;
for (int i = 0; i < arr.length; i++) {
if (visited[i] == true) {
continue;
}
if(before != arr[i]){
visited[i] = true;
result[cnt] = arr[i];
before = arr[i];
dfs(cnt + 1);
visited[i] = false;
}
}
}
}