백준 알고리즘 파이썬(Python) 10972번 다음 순열

---

 

이 문제는 next_permutation 문제이다.

 

next_permutation이란 무엇인가?

현재 순열의 상태에서 크기순으로(사전 순) 다음에 올 수 있는 순열을 생성해주는 역할을 한다.

 

예를 들어 1, 4, 3, 2라는 수가 있을 때

1 4 3 2 -> 2 4 3 1 -> 2 1 4 3 ~ 식으로 순열을 만들어주는 역할을 수행한다.

 

 

1 4 3 2의 경우

1. 뒤에서부터 순열을 비교, 뒷 값이 앞 값보다 큰 경우까지 반복한다. -> 여기서는 (1, 4)가 해당
2. 이때 1의 인덱스를 x라고 하고 4의 인덱스를 y라고 한다.
3. 다시 두 번째 for 문으로부터 탐색하여 인덱스 x값 즉 1 보다 큰 값이 있으면 그 값과 1을 swap 한다. -> 여기서는 1과 2가 swap
4. y에 해당하는 인덱스부터 정렬해준 뒤 이어 붙여준다. -> 여기서는 4 3 1을 정렬해준 1 3 4가 이어붙어 2 1 3 4가 되게 된다.

 

---

# next_permutation 파이썬 구현

n = int(input())
arr = list(map(int,input().split()))

x, y = 0, 0
a = True
for i in range(n-1, 0, -1):
    if arr[i] > arr[i-1]:
        x, y = i-1, i
        for j in range(n-1, 0, -1):
            if arr[j] > arr[x]:
                arr[j], arr[x] = arr[x], arr[j]
                a = False
                break
    if a == False:
        arr = arr[:y] + sorted(arr[y:])
        print(*arr)
        break
if a == True:
    print(-1)

 

 

참고로 이중 for문을 탈출할 때는 a = True로 처음 설정해 두는 방법을 사용하였다.

https://gomguard.tistory.com/190를 참고하면 방법이 자세히 나와있다.