[백준/Python] 다음 순열

문제

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

---

문제 요약

1부터 N까지 수로 이루어진 순열에서 한 개의 순열을 입력 받고, 사전순으로 다음에 오는 순열을 출력한다.

---

코드

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

for i in range(N - 1, 0, -1):  # 마지막 요소부터 접근
    if arr[i - 1] < arr[i]:  # 앞 요소보다 더 크다면
        for j in range(N - 1, 0, -1):  # 앞 요소를 다시 마지막 요소부터 비교
            if arr[i - 1] < arr[j]:  # 앞 요소가 뒤에 있는 어느 요소(arr[j])보다 작다면
                arr[i - 1], arr[j] = arr[j], arr[i - 1]  # 두 값 위치 교체
                arr = arr[:i] + sorted(arr[i:])  # i-1 번째 까지의 리스트와 그 뒤 리스트를 정렬하고 붙인다.
                print(*arr) 
                exit()  # 코드 종료

print(-1)  # 만약 위에서 코드 종료가 일어나지 않았다면(순열의 마지막이라면) -1 출력

---

코드 설명

파이썬의 permutation 함수와 재귀 함수를 이용한 백트래킹 방식으로 이 문제를 풀 경우 모두 시간 초과가 발생한다.

 

따라서 새로운 알고리즘으로 문제를 풀어야한다.

 

다음 순열을 찾는 알고리즘은 다음과 같다. (입력 예시: 1 4 3 2)

 

1. 뒤에서부터 요소을 접근하여, 뒷 요소(arr[i])가 앞 요소(arr[i-1])보다 큰 경우를 찾는다.

- (3, 2), (4, 3)은 해당하지 않고, (1, 4)가 해당한다.

- 앞 요소는 1, 뒷 요소는 4이다.

 

2. 다시 뒤에서부터 요소를 접근하여, 앞 요소보다 큰 요소를 찾으면 그 값과 앞 요소의 위치를 변경한다.- 1과 2를 비교하여 2가 더 크므로 두 요소의 위치를 변경한다.- 1 4 3 2 -> 2 4 3 1이된다.

 

4. 뒷 요소에 해당하는 인덱스부터 마지막 요소까지 오름차순하고 앞 요소에 이어 붙인다.- 4 3 1를 오름차순하여 1 3 4를 만들고 앞요소인 1에 이어 붙여 2 1 3 4가 된다.