문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 2
4 2예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3예제 입력 3
4 4예제 출력 3
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1풀이
import java.util.Scanner;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected;
private static void rec_func(int k) {
if(k == M + 1) { // 다 골랐다
// selected[1...M] 배열이 새롭게 탐색된 결과
for(int i=1; i<=M; i++){
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
//
for (int cand = 1; cand <= N; cand++) {
boolean isUsed = false;
for(int i=1; i<=k; i++){
if (selected[i] == cand) {
isUsed = true;
}
}
// k 번째에 cand 가 올 수 있으면
if(!isUsed) {
selected[k] = cand;
rec_func(k + 1);
selected[k] = 0;
}
}
}
}
public static void main(String[] args) {
input();
// 1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법을 찾아줘
rec_func(1);
System.out.println(sb.toString());
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
selected = new int[M + 1];
}
}
심화
import java.util.Scanner;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected, used;
// Recurrence Function (재귀 함수)
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것
// 아직 M개를 고르지 않음 => k번째부터 M번쨰 원소를 조건에 맞게 고르는 방법을 시도한다
private static void rec_func(int k) {
if(k == M + 1) { // 다 골랐다
// selected[1...M] 배열이 새롭게 탐색된 결과
for(int i=1; i<=M; i++){
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
if(used[cand] == 1){
continue;
}
// k 번째에 cand 가 올 수 있으면
selected[k] = cand; used[cand] = 1;
rec_func(k + 1);
selected[k] = 0; used[cand] = 0;
}
}
}
public static void main(String[] args) {
input();
// 1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법을 찾아줘
rec_func(1);
System.out.println(sb.toString());
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
selected = new int[M + 1];
used = new int[N + 1];
}
}for문이 두 번 쓰이면 시간복잡도가 증가한다.
체크배열로 이미 사용된 숫자인지 확인하는 방법으로 심화해본다.
