[백준] 10974번 (python 파이썬) 모든 순열

n이 주어지면 1부터 n까지의 수열을 만들어서 사전순으로 출력해주는 문제이다.

중복은 없어야한다.

 

두 가지 방법으로 풀어봤는데

첫번째는 방문했는지 안했는지의 여부에 따라 빈 리스트에 추가하는 방법

두번째는 다음 순열의 규칙을 활용하는 방법을 사용하였다.

두 방법의 시간 차이는 없다고 보면 된다.

def solve(idx):
    if idx == n:
        print(' '.join(map(str, lst)))
        return
    for x in range(1, n + 1):
        if check[x]:
            continue
        check[x] = True
        lst.append(x)
        solve(idx + 1)
        check[x] = False
        lst.pop()
        
n = int(input())
lst = []
check = [False] * (n + 1)
solve(0)

def solve(lst):
    for i in range(n - 1, 0, -1):
        if lst[i - 1] < lst[i]:
            for j in range(n - 1, 0, -1):
                if lst[i - 1] < lst[j]:
                    lst[i - 1], lst[j] = lst[j], lst[i - 1]
                    lst = lst[:i] + sorted(lst[i:])
                    return lst
                
n = int(input())
lst = list(range(1, n + 1))
rlst = sorted(lst, reverse = True)
print(' '.join(map(str, lst)))
while True:
    if lst == rlst:
        break
    lst = solve(lst)
    print(' '.join(map(str, lst)))