백준 10974 파이썬 python : 모든 순열 @@황소처럼 우직하게@@ permutations 구현할 때, 이 코드 참고하세요~

n = int(input())

def next_permutation(lst):
    n = len(lst)
    i = n - 1
    while i > 0 and lst[i - 1] >= lst[i]:
        i -= 1
    if i <= 0:
        return [-1]
    # i - 1인덱스하고
    j = n - 1
    while lst[j] <= lst[i - 1]:
        j -= 1
    # j 인덱스하고 바꾼다.
    tmp = lst[j]
    lst[j] = lst[i - 1]
    lst[i - 1] = tmp

    lst = lst[:i] + sorted(lst[i:])
    return lst

ans = [i for i in range(1, n + 1)]
while True:
    if ans == [-1]:
        break
    print(' '.join(map(str, ans)))
    ans = next_permutation(ans)

시간복잡도는 O(N * N!) 이다.

너무크다고?

수 범위가 8이하기에 시간초과는 나지않는다.