[백준] 10974번 : 모든 순열 풀이(python)

✅문제

출처 : 백

✅문제 풀이 

1. A[i-1] < A[i] 인 가장 큰 i 찾기

2. j >= i 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j 찾기

3. A[i-1], A[j] 스왑

4. A[i] 부터 순열을 뒤집기

 

ex)

7236541

1. 가장 큰 i 는 6

   → A[i-1] = 3

2.  A[i-1]이 3 이기 때문에 3보다 크면서 가장 큰 j 찾기 

   → A[j] = 4

3. A[i-1], A[j] 스왑 

   → 7246531

4. A[i] 부터 순열 뒤집기

   → 7241356 

 

✅Code

def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i] <= a[i-1]:
        i -= 1
    if i <= 0:
        return False

    j = len(a)-1
    while a[j] < a[i-1]:
        j -= 1

    a[j], a[i-1] = a[i-1], a[j]

    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

def prev_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] <= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] >= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

n = int(input())
a = list(range(1, n+1))

print(' '.join(map(str, a)))
while next_permutation(a):
    print(' '.join(map(str, a)))