문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 시간 제한 : 1초
- 메모리 제한 : 512MB입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근 방법
위 문제에서 생성할 수 있는 수열의 수는 N^M이므로 시간복잡도는 O(N^M)입니다. 최악의 경우는 N과 M 모두 7인 경우로 총 823,543가지의 경우가 나오므로 1초의 시간 제한을 넘지 않고 Brute Force로 해결이 가능합니다.
문제를 해결하기 위해 우선 예를 들어 N = 4, M = 3인 경우를 생각해보겠습니다. 이와 같은 경우 111, 112, 113, ...처럼 처음 두 자리를 고정 시킨 뒤 가장 마지막 자리를 바꿔가며 수열을 만들게 되고 마지막 자리의 수를 바꿔서 새로운 수열을 생성할 수 없는 경우 앞 자리의 수를 변경하게 반복하게 됩니다. 이를 for 문을 이용하여 나타내면 아래와 같을 것입니다.
for (int i = 1; i <= n, ++i) // 첫번째 자리
for (int j = 1; j <= n; ++j) // 두번째 자리
for (int k = 1; k <= n; ++k) // 세번째 자리
// 수열 출력
System.out.println(i + " " + j + " " + k);하지만 M 또한 입력으로 받아서 for 문만 이용하여 구현하기는 어려우므로 재귀 함수를 통하여 구현을 해야합니다. 재귀 함수를 통하여 우선 첫째 자리의 수를 결정 후 함수를 다시 호출하여 둘째 자리를 결정하고 또 다시 함수를 호출하여 그 다음 자리를 결정하는 방식으로 구현할 수 있습니다.
// rec은 재귀 함수가 몇번 호출된 횟수
// 배열의 index는 0부터 시작하므로 처음 호출 시 rec은 0
static void func(int rec) {
for (int i = 1; i <= n; ++i) {
selected[rec] = i; // rec번째 자리 수를 결정
func(rec + 1); // 그 다음 자리 수를 결정할 함수 호출
}
}
이를 이용하여 전체 코드를 작성하면 아래와 같습니다.
코드
import java.util.*;
public class Main {
private static int n;
private static int m;
private static int[] selected;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
input(); // 입력 값을 받는 함수
func(0); // 재귀 함수로 결과를 생성하는 함수
System.out.println(sb); // 결과 출력
}
private static void input() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
selected = new int[m]; // m자리의 수열이므로
sc.close();
}
private static void func(int rec) {
// 마지막 자리까지 수를 고른 경우
if (rec == m) {
// 해당 수열을 StringBuilder로 결과에 추가
for (int i : selected) {
sb.append(i).append(" ");
}
sb.append('\n');
return;
}
// 아직 수를 골라야할 자리가 존재하는 경우
// 1부터 n까지의 자연수에서 순서대로 수를 결정
for (int i = 1; i <= n; ++i) {
selected[rec] = i; // 해당 자리의 수 결정
func(rec + 1); // 재귀를 통하여 다음 자리 결정
}
}
}주의할 점
모든 자리의 수를 결정하였다고 해서 println으로 바로 출력을 하게 되면 시간 초과가 발생합니다. 그 이유는 IO 연산은 시간이 많이 걸리기 때문으로 IO 연산을 최소화하기 위하여 StringBuilder를 이용하여 마지막에 한번만 println을 호출 하는 것을 볼 수 있습니다.
