728x90
문제
* N개의 숫자 중 M개를 구하는 방법
* 단, N개의 숫자 중 중복이 있을 수 있고,
* 같은 차례에 있는 숫자는 중복선택이 불가함
원리
1. 백트래킹 (DFS)
2. 재귀
풀이방법
재귀를 이용한 풀이
* 1. 입력받은 수들을 ArrayList에 담고, 오름차순 정렬
* 2. Combination(재귀 메소드)를 이용해 0번째부터 카운트하며 재귀 시작
* 3. 뽑아야 하는 개수 M이 되기 전까지 재귀를 통한 반복문을 진행
* 4. 중복을 제거하기위해 방문 체크를 시행(visited) -> 방문 후 재귀를 시행
* 5. 방문한 곳에대한 재귀로 해당 경우의 수를 모두 구한 뒤, 다시 방문을 해제하여 다른 경우에서 방문할 수 있도록 허용해줌
* 6. 모든 경우의 수를 구한 뒤, 같은 경우에 대해 중복 제거 실행
* 7. 최종적으로 구해진 모든 경우의 수를 출력
나의 코드
1. [실패] 재귀사용 : 중복 선택이 허용된 코드가 되어버림
더보기
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static List<Integer> nums = new ArrayList<>();
private static int[] subset;
private static List<String> results = new ArrayList<>();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
subset = new int[M];
StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
for(int i =0; i<N ; i++) nums.add(Integer.parseInt(numbers.nextToken()));
// nums = nums.stream().distinct().sorted().collect(Collectors.toList()); // 중복된 항목을 제거 후 수열을 구하는 방법
Collections.sort(nums);
Combination(0, 0);
results = results.stream().distinct().collect(Collectors.toList());
bw.close();
}
private static void Combination(int cnt, int k) throws IOException {
if(cnt==M) {
String str = "";
for(int i = 0; i<M ; i++) str += subset[i] + " ";
results.add(str);
return;
}
for(int i=k ; i<N ; i++) {
subset[cnt] = nums.get(i);
// Combination(cnt+1, i);
Combination(cnt+1, k);
}
}
2. [실패] visited를 이용해 중복을 제거 시도 -> 테스트 코드는 성공, 제출에서 틀림
: 5 3, 1 3 5 7 9 로 실행시 왜 틀렸는지 알 수 있음 (visited 문제)
더보기
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static List<Integer> nums = new ArrayList<>();
private static int[] subset;
private static List<String> results = new ArrayList<>();
private static boolean[] visited;
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
subset = new int[M];
visited = new boolean[N];
StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) nums.add(Integer.parseInt(numbers.nextToken()));
Collections.sort(nums);
Combination(0, 0);
results = results.stream().distinct().collect(Collectors.toList());
for (int i = 0; i < results.size(); i++) bw.write(results.get(i) + "\n");
bw.close();
}
private static void Combination(int cnt, int k) {
if (cnt == M) {
String str = "";
for (int i = 0; i < M; i++) str += subset[i] + " ";
results.add(str);
int visitCnt = 0;
for(int i=0;i<visited.length; i++) if(visited[i]) visitCnt++;
if(visitCnt==visited.length) visited = new boolean[N];
return;
}
for (int i = k; i < N; i++) {
if(!visited[i]) {
subset[cnt] = nums.get(i);
visited[i] = true;
Combination(cnt + 1, k);
}
}
}
3. [성공] 방문 체크를 위한 위치가 문제였음
: 방문 체크 후 재귀를 돌리고, 재귀가 끝난 다음 다시 방문 해제해주는 원리로 해결
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
public class no15667 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static List<Integer> nums = new ArrayList<>();
private static int[] subset;
private static boolean[] visited;
private static List<String> results = new ArrayList<>();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
subset = new int[M];
visited = new boolean[N];
StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) nums.add(Integer.parseInt(numbers.nextToken()));
// nums = nums.stream().distinct().sorted().collect(Collectors.toList()); // 중복된 항목을 제거 후 수열을 구하는 방법
Collections.sort(nums);
Combination(0);
results = results.stream().distinct().collect(Collectors.toList());
for (int i = 0; i < results.size(); i++) bw.write(results.get(i) + "\n");
bw.close();
}
private static void Combination(int cnt) {
if (cnt == M) {
String str = "";
for (int i = 0; i < M; i++) str += subset[i] + " ";
results.add(str);
return;
}
for (int i = 0; i < N; i++) {
if(!visited[i]) {
subset[cnt] = nums.get(i);
visited[i] = true; // 방문 체크 후, 재귀를 돌리고
Combination(cnt + 1);
visited[i] = false; // 재귀가 끝나면 해당 부분은 다시 방문 해제 (여기가 포인트)
}
}
}
}
Chat GPT 코드
필자의 첫번째 코드와 같이 중복된 코드를 솎아내지 못한다.
더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class no15667 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line1 = br.readLine().split(" ");
int n = Integer.parseInt(line1[0]);
int m = Integer.parseInt(line1[1]);
int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(nums); // sort the input numbers in ascending order
List<String> res = generateSequence(nums, m, new ArrayList<>()).stream().distinct().sorted().collect(Collectors.toList());
for (String seq : res) {
System.out.println(seq);
}
}
public static List<String> generateSequence(int[] nums, int m, List<Integer> cur) {
if (cur.size() == m) {
StringBuilder sb = new StringBuilder();
for (int num : cur) {
sb.append(num).append(" ");
}
return Arrays.asList(sb.toString().trim());
}
List<String> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
cur.add(nums[i]);
res.addAll(generateSequence(nums, m, cur)); // recursively generate the sequence
cur.remove(cur.size() - 1);
}
return res;
}
}
728x90
'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글
| [백준] no11053: 가장 긴 증가하는 부분 수열 - 최장 증가 부분 수열 (LIS) (0) | 2023.05.05 |
|---|---|
| [백준] no15666: N과 M (12) - 비내림차순 구하기(중복허용/visited 제거) (0) | 2023.05.01 |
| [백준] no15657: N과 M (8) - 중복 Combination (0) | 2023.04.29 |
| [백준] no15654: N과 M (5) (0) | 2023.04.28 |
| [백준] no15650, 15652: N과 M (2, 3) - 기본 Combination 문제 (0) | 2023.04.26 |