[Java+Python]15651번, N과 M(3), 중복순열

Java+Python으로 순열/조합/중복순열/중복조합 구현하기

 

[Java+Python]15649번, N과 M(1), 순열

[Java+Python]15650번, N과 M(2), 조합

[Java+Python]15651번, N과 M(3), 중복순열

[Java+Python]15652번, N과 M(4), 중복조합

 

문제

 

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

 

출력

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 

중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

 

중복순열은 순열 중에서도 같은 숫자를 뽑는 것을 허용하는(예를 들면 1 1 같은) 순열이다.

 

당연하게도 경우의 수는 기존의 일반 순열에 비해 많지만,

 

여기서는 그 개수를 계산하지는 않겠다.

 

구현에 있어서는 기존 순열을 아주 조금만 변경하면 되는데,

 

이미 방문했던 노드로의 방문을 금지하는 isVisited 사용을 중지하면 된다.

 

그렇게 하면 모든 노드를 m만큼 반복하게 되고,

 

원하는 결과를 얻을 수 있다.

 

먼저 자바 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Prob15651_4 {
	static int n;
	static int m;
	static int[] arr;
	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());
		arr = new int[m];

		dfs(0);

		System.out.println(sb);
	}

	private static void dfs(int depth) {
		if (depth == m) {
			for (int num : arr) {
				sb.append(num).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = 1; i <= n; i++) {
			arr[depth] = i;
			dfs(depth + 1);
		}
	}
}

다음은 파이썬 코드.

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
lst = [0 for _ in range(m)]
memo = [False for _ in range(n + 1)]


def dfs(depth):
    if depth == m:
        for i in lst:
            print(i, '', end='')
        print()
        return
    for i in range(1, n + 1):
        lst[depth] = i
        dfs(depth + 1)


dfs(0)

자바와 다른 점이 있다면, sb와 같은 전역 변수를 만들어 하나의 긴 문자열을 만든 뒤 출력하려고 할 때

 

오히려 시간초과가 난다는 점이다.

 

그리고 평균 실행시간이 수상할 정도로 길다.. 만 나는 해결책을 찾지 못했다.