문제
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
DFS 이용하여 모든 인덱스 순회 함.
코드
import java.util.Scanner;
public class Main {
static StringBuilder sb = new StringBuilder();
static StringBuilder result = new StringBuilder();
public static void dfs(int[] arr, boolean[] visited, int depth, int index, int d) {
visited[index] = true;
sb.append(arr[index]+" ");
if (depth == 1) {
result.append(sb + "\n");
return;
}
for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
dfs(arr, visited, depth-1, i, d);
visited[i] = false;
sb.delete(sb.length()-2, sb.length());
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int[] arr = new int[a];
boolean[] visited = new boolean[a];
for (int i = 0; i < a; i++) {
arr[i] = i+1;
}
for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
dfs(arr, visited, b, i, b);
visited[i] = false;
sb.setLength(0);
}
}
System.out.println(result);
}
}
StringBuilder 변수를 두개 이용하여 출력을 1회로 수정 후 시간이 1220ms → 268ms 로 많이 줄었다.
'알고리즘' 카테고리의 다른 글
| [백준] 16234번 인구 이동 자바 풀이 (0) | 2023.08.17 |
|---|---|
| [백준] 2615번 오목 자바 풀이 (0) | 2023.08.01 |
| [백준] 1244번 스위치 켜고 끄기 풀이 (0) | 2023.08.01 |
| [백준] 2002번 추월 자바 풀이 (0) | 2023.07.25 |
| [백준] 14400번 편의점 2 자바 풀이 (0) | 2023.07.25 |
