반응형
🔺 문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
🧩 해결 아이디어
• 백트래킹 (조합)
- 마지막으로 뽑힌 숫자와 지금까지 뽑은 갯수를 값으로 가져가서 뽑을 수 있는 원소 후보들을 탐색한다.
- 시간 복잡도: O(M)
🔺 코드
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
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] arr;
static List<Integer> combList = new ArrayList<>(); // 조합 리스트
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());
comb(1, 0);
System.out.println(sb);
}
private static void comb(int lastNum, int depth) { // 마지막으로 뽑힌 숫자, 지금까지 뽑은 갯수 저장
// M개 뽑았을 때, 출력
if(depth == M) {
print();
return;
}
// 뽑을 수 있는 원소 후보들 탐색
for(int i = lastNum ; i <= N ; i++) {
combList.add(i);
comb(i + 1, depth + 1);
combList.remove(combList.size() - 1);
}
}
// 조합 리스트 출력 메소드
private static void print() {
for(int i = 0 ; i < combList.size() ; i++) {
sb.append(combList.get(i)).append(" ");
}
sb.append("\n");
}
}
|
cs |
🔺 다른 풀이들
- 2^N 재귀 생성 : 현재 숫자를 뽑을지 말지 경우의 수 나눠 탐색
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
|
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static int n, m;
public static ArrayList<Integer> combination = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
findCombination(1, 0);
}
// 지금까지 뽑은 갯수와 뽑을지 말지를 결정할 숫자를 인자로 받음
public static void findCombination(int currNum, int cnt) {
// n개의 숫자를 모두 탐색했으면, 탐색 중지
if(currNum == n+1) {
// 탐색 과정에서 숫자 m개 뽑은 경우 답 출력
if(cnt == m)
printCombination();
return;
}
// case 1) idx에 해당하는 숫자 "사용했을 때" 탐색
combination.add(currNum);
findCombination(currNum + 1, cnt + 1);
combination.remove(combination.size() - 1);
// case 2) idx에 해당하는 숫자 "사용하지 않았을 때" 탐색
findCombination(currNum + 1, cnt);
}
// 방문한 원소들 출력 메소드
public static void printCombination() {
for(int i = 0; i < combination.size(); i++)
System.out.print(combination.get(i) + " ");
System.out.println();
}
}
|
cs |
💬 느낀 점
해당 번호 뽑거나 안 뽑거나 한 경우를 이렇게 나누는 거구나...!!!
여태 문제 풀면서 몰랐는데 이렇게 재귀를 이제서야 좀 온전히 파악하다....ㅠ
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 12.20 |
(참고)
✔ 코드트리
반응형
'코테 > 코드트리' 카테고리의 다른 글
[코드트리/INTERMEDIATE LOW] 크기가 n인 순열 (JAVA) (1) | 2023.12.05 |
---|---|
[코드트리/INTERMEDIATE LOW] xor 결과 최대 만들기 (JAVA) (0) | 2023.12.05 |
[코드트리/INTERMEDIATE LOW] 사각형 채우기 2 (JAVA) (0) | 2023.11.28 |
[코드트리/INTERMEIDATE LOW] 정수 사각형 최대 합 (JAVA) (0) | 2023.11.26 |
[코드트리/INTERMEIDATE LOW] 사각형 채우기 3 (JAVA) (0) | 2023.11.26 |