[백준10974번] 모든 순열 / Python3

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1

3

예제 출력 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

나의 풀이

10972번 다음 순열 문제를 풀었다면 응용하여 풀 수 있다. 1부터 n까지의 리스트를 만들고, 다음 순열을 구하는 함수와 순열을 print해주는 함수를 만들어 k가 -1이 나올때까지 반복을 해주었다.

코드

# 10974번 모든 수열

# 순열 찾기
def find(bs):
    k = -1
    # 1. k의 최댓값 구하기
    for i in range(len(bs)-1):
        if bs[i] < bs[i+1]:
            k = i

    # 마지막
    if k == -1:
        return -1

    # 2. m의 최댓값 구하기
    for j in range(k+1,len(bs)):
        if bs[k] < bs[j]:
            m = j

    # 3. k와 m 바꿔치기
    bs[k], bs[m] = bs[m], bs[k]

    # 4. k 이후 오름차순으로 정렬
    tmp = bs[k+1:]
    tmp.sort()
    return bs[:k+1] + tmp

# print
def printSeq(s):
    for num in s:
        print(num, end=' ')
    print()

# main
n = int(input())

seq = [x for x in range(1,n+1)]

while True:
    printSeq(seq)
    seq = find(seq)

    if seq == -1:
        break