알고리즘 (with JAVA)/완전 탐색
n개의 원소 중 m개를 고르는 순열과 조합
백_곰
2022. 8. 29. 11:14
1. 문제 설명
(1) N개의 정수들 중에 M개를 고르는 (중복을 허용하는) 순열을 구하시요.
--> permDup() 메서드로 구현하여라.
(2) N개의 정수들 중에 M개를 고르는 (중복을 허용하지 않는) 순열을 구하시오.
--> permNotDup() 메서드로 구현하여라.
(3) N개의 정수들 중에 M개를 고르는 조합을 구하시오.
--> combi() 메서드로 구현하여라.
2. 풀이 및 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
public class Main{
static int N, M, ans;
static int[] map;
static boolean[] visited;
static ArrayList<Integer> arr;
public static void main(String[] args) throws Exception{
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(sc.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
solve();
}
public static void solve() {
System.out.println("-----중복 있는 순열-----");
map = new int[M];
permDup(0);
System.out.println("-----중복 없는 순열-----");
map = new int[M];
visited = new boolean[N+1];
permNotDup(0);
System.out.println("-----조합-----");
arr = new ArrayList<>();
combi(0);
}
public static void permDup(int depth) {
if(depth==M) {
for(int i=0; i<M; i++) {
System.out.print(map[i]+" ");
}
System.out.println();
return;
}
for(int i=1; i<=N; i++) {
map[depth]=i;
permDup(depth+1);
}
}
public static void permNotDup(int depth) {
if(depth==M) {
for(int i=0; i<M; i++) {
System.out.print(map[i]+" ");
}
System.out.println();
return;
}
for(int i=1; i<=N; i++) {
if(!visited[i]) {
visited[i]=true;
map[depth]=i;
permNotDup(depth+1);
visited[i]=false;
}
}
}
public static void combi(int depth) {
if(depth==M) {
for(int i=0; i<M; i++) {
System.out.print(arr.get(i)+" ");
}
System.out.println();
return;
}
int here = arr.isEmpty()?1:arr.get(arr.size()-1)+1;
for(int i=here; i<=N; i++) {
arr.add(i);
combi(depth+1);
arr.remove(arr.size()-1);
}
}
}
|