문제 / 중복순열 구하기 ( itertools product ) / Python 파이썬

coding test - python/기본기 문제

문제 / 중복순열 구하기 ( itertools product ) / Python 파이썬

sillon 2022. 10. 13. 19:55

728x90

문제 제목: 중복 순열 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명

첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다. ▣ 입력예제

3 2

▣ 출력예제

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

나의 풀이

from itertools import product
def solution(n,m):

    arr = [ i for i in range(1,n+1)]
    cnt = 0

    for i in product(arr, repeat = m):
        cnt += 1
        answer = ""
        for j in i:
            answer += str(j)
            answer += " "
        print(answer[:-1])



    return cnt

if __name__ == "__main__":
    n, m = map(int,input().split())

    print(solution(n,m))

모범답안 - DFS 풀이

import sys
sys.stdin=open("input.txt", "r")
def DFS(L):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            res[L]=i
            DFS(L+1)

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*m
    cnt=0
    DFS(0)
    print(cnt)