순열 구하기

문제 포인트

• 1~N 번호가 적힌 구슬 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력
• 맨 마지막에는 총 경우의 수를 출력
• 출력 순서는 사전순으로 오름차순으로 출력

my_solution

from itertools import permutations

n, m = map(int, input().split())
beads = [i for i in range(1, n + 1)]
beads_per = tuple(permutations(beads, m))

for bead in beads_per:
    print(*bead, end=" ")
    print()
print(len(beads_per))

• 순열을 구하는 문제이기 때문에 itertools.permutations 사용

solution

res = [0] * n
ch = [0] * (n + 1)
cnt = 0


def recursive(level):
    global cnt
    if level == m:
        for j in range(level):
            print(res[j], end=" ")
        print()
        cnt += 1
    else:
        for i in range(1, n + 1):
            if ch[i] == 0:
                ch[i] = 1
                res[level] = i
                recursive(level + 1)
                ch[i] = 0  # 다시 초기화해줘야 다음 탐색에서 해당 숫자일 때 탐색 가능


recursive(0)
print(cnt)

• 재귀적으로 구현
• 중복을 허용하지 않기 때문에 중복으로 가지가 뻗어나가지 않도록 이를 체크할 수 있는 체크 배열을 생성하여 문제 해결