[코딩테스트 공부] N과 M (중복순열)

출처 : https://www.acmicpc.net/problem/15651

풀기 전에 할 말

이번에 이 문제는 이전에 Java 언어로 푼 것과는 달리, Python으로 풀었습니다. 코드가 매우 간결합니다 :)

일단 코드부터 보실래요?

def recursiveFunc(k, sequence):
    # 탈출 조건
    if(k == M):
        print(sequence)
        return
    
    # 점화 관계
    for i in range(1, N + 1):
        sequence_param = sequence + str(i) + " "
        recursiveFunc(k + 1, sequence_param)
        
N, M = map(int, input().split(" "))
recursiveFunc(0, "")

코드에 대한 설명

언제나 그래왔듯, 이러한 완전탐색(brute force) 유형은 재귀함수로 푸는 것이 일반적입니다. 탈출 조건과, 점화 관계에 대해서 설명을 드릴게요.

탈출 조건

탈출 조건의 경우, 그저 탐색이 끝나면 출력을 해주고 끝내면 된답니다. 매우 간단하죠? 그래서 k와 M이 일치만 해주면 탈출!

점화 관계

위의 재귀함수는, 숫자만 붙여주고 다음 시퀀스로 넘어가면 되기 때문에, 파라미터로 k + 1, 뒤에 숫자를 붙인 sequence_param을 전달하면 끝납니다.

제가 제시한 코드의 복잡도는?

결과적으로 말씀드리면, 저의 코드 복잡도는 N^M입니다. 이유는, 위의 문제는 중복순열을 요구하였기 때문에, N개의 숫자가 각자 M번 등장이 가능하기 때문입니다.

이번 코드는 너무 간단했습니다... 다음에는 더 재밌는 문제로 찾아올게요!