문제
N개의 자연수 중에서 M개를 고른 수열을 모두 출력하는 문제이다. 단, 같은 수를 중복해서 선택할 수 있다. 수열은 사전 순으로 증가하는 순서로 출력한다. 임의의 N개 자연수를 중복 허용하여 M개 수열을 만드는 중복 순열(중복 있는 순열) 문제이다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 10,000보다 작거나 같다.
출력
한 줄에 하나씩, 중복 허용 M개짜리 수열을 모두 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 3 1 4 | 1 3 4 |
3 2 3 1 4 | 1 1 1 3 1 4 3 1 3 3 3 4 4 1 4 3 4 4 |
풀이
N개의 자연수 중 M개를 고르는 중복 순열을 백트래킹으로 열거한다. 중복을 허용하므로 방문 체크 없이 매 단계에서 N개 원소 전체를 다시 탐색한다.
- 입력받은 N개의 수를
Arrays.sort()로 오름차순 정렬한다. comb(d)재귀 함수를 호출한다.d는 현재 선택 깊이이다.d == M이면 선택된 배열sel을 출력하고 반환한다.- 매 단계에서 0부터 N-1까지 모든 인덱스를 순회한다. 방문 체크를 하지 않아 같은 수를 반복 선택할 수 있다.
sel[d] = arr[i]로 선택 후comb(d+1)재귀 호출한다.
핵심 아이디어: 중복 순열은 방문 배열이 필요 없다. 매 재귀 단계마다 전체 배열을 처음부터 탐색하면 자연스럽게 중복 선택이 가능해진다. 시작 인덱스 제한이 없으므로 이전 단계에서 선택한 원소를 다시 고를 수 있다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Day57BOJ15656N과M7중복허용조합 {
static int N, M;
static int[] arr, sel;
static StringBuilder sb;
static List<String> ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
sel = new int[M];
sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
comb(0);
System.out.println(sb);
br.close();
}
private static void comb(int d) {
if (d == M) {
sb.append(Arrays.toString(sel).replaceAll("[\\[\\],]", "").trim()).append("\n");
return;
}
for (int i = 0; i < N; i++) {
sel[d] = arr[i];
comb(d + 1);
}
}
}복잡도
- 시간: O(N^M) — 중복 순열의 수 (N개 중 중복 허용하여 M개 선택)
- 공간: O(M) — 재귀 스택 깊이 M, 선택 배열 M