[백준/Python3] 10972 다음 순열

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

풀이

N 길이의 순열이 주어질 때 그 다음 순열을 출력하고 만약 마지막 순열이었다면 -1을 출력하는 문제다. 처음에는 제한을 미처 보지 못하고 바로 파이썬에 내장된 permutations로 모든 순열을 만들어 맞는 것의 인덱스를 출력하게끔 했다. 하지만 이렇게 될 경우 1 <= N <= 10000, O(N^2) 때문에 메모리 초과, 시간 초과 등 여러 문제가 발생할 수 있다. 때문에 이번 문제에는 Next Permutation 알고리즘을 사용한다.

Next Permutation 알고리즘은 C++ 경우 stl에 내장되어 있지만 Python에는 그렇지 않으므로 직접 구현해야 한다. 이번 기회에 제대로 정리해두자.

문제의 예제 1번인 N = 4인 순열을 만들어보자.
이때, 첫 번째 순열은 1 2 3 4이며 아래와 같이 이어진다.

1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> ... -> 4 3 2 1

1 2 3 4 -> 1 2 4 3 과정

제일 뒤에서부터 탐색하여 앞 숫자가 뒷 숫자보다 작아지는 경우를 찾는다. 위 경우 (3, 4)에서 찾을 수 있다. 이때 3보다 큰 값이 나오는지 맨 뒤에서부터 찾기 시작하면 4가 나온다. 이 둘을 스왑할 경우 1 2 4 3이 된다.

1 2 4 3 -> 1 3 2 4 과정

같은 방법으로 앞 숫자가 뒷 숫자보다 작아지는 경우를 찾는다. 위 경우 (2, 4)에서 찾을 수 있다. 이때 2보다 큰 값이 나오는지 맨 뒤에서부터 찾기 시작하며 이는 3이다. 이때 이 둘의 값을 스왑하며 결과로는 1 3 4 2가 나온다. 값을 바꾼 3을 기준으로 1 3 4 2로 나눈 뒤 앞의 값 1 3과 뒤의 값을 정렬한 결과인 2 4를 합친다. 결과적으로 1 3 2 4가 나오게 된다.

따라서 다음 순열을 구하는 알고리즘은 아래와 같이 나타난다.

1. 수열을 맨 뒤에서 탐색하기 시작하여 앞 숫자가 뒷 숫자보다 작아지는 경우가 있는지 찾는다.
2. 작아지는 경우가 있을 경우 그 숫자를 기준으로 잡는다. 이후 맨 뒤에서 탐색하기 시작해 기준보다 큰 숫자가 있는지 확인한다.
3. 더 큰 숫자가 있다면 기준이 되는 숫자와 큰 숫자의 스왑한다.
4. 기준이 되는 숫자로 앞과 뒤를 나누어 앞 수열은 그대로 뒷 수열은 정렬한 뒤 이 수열들을 합친다.

결과로 주어진 순열의 다음 순열을 구할 수 있다.

코드

import sys
input = sys.stdin.readline

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[i-1], arr[j] = arr[j], arr[i-1] # 그 두 값을 스왑
                arr = arr[:i] + sorted(arr[i:])
                print(*arr)
                exit()

print(-1)

참고

아래는 참고한 홈페이지입니다. 감사합니다.
https://ji-gwang.tistory.com/262
https://velog.io/@tomato2532/NextPermutation