[백준] 10972번 다음 순열 (by Python)

문제

언뜻 보면 단순한 문제이지만, 내게는 그리 단순하지 않았다. 순열이 나열되는 순서를 논리적으로 표현하는 것에서 어려움을 겪었기 때문이다. 그렇기 때문에 처음에는 permutations 라이브러리를 사용해서 단순하게 해결하려고 시도를 했다.

 

첫 번째 풀이

from itertools import permutations

n = int(input())
target = list(map(int, input().split()))
array = list(map(list, permutations(range(1, n + 1))))
answer = array.index(target)

if answer == len(array) - 1:
    print(-1)
else:
    for i in array[answer + 1]:
        print(i, end=' ')

 

이 경우, 라이브러리가 잘 작동해주었지만, 10000까지의 수의 순열은 가짓수가 굉장히 많다는 것을 간과한 나머지, 메모리 초과로 실패해버렸다. 그리고 나서, 나는 정말로 어떻게 '다음 순열'로 가는 방법을 찾을 수 있을지 고민하게 되었다.

 

두 번째 풀이

원리는 다시 생각해보면 간단했다. 1부터 n까지의 수로 이루어진 순열들이니, 모든 수가 다 다르다고 할 수 있다. 그렇다면 결국 순열들의 순서는 이 수들로 만들 수 있는 수들의 오름차순 나열인 것이다. 결과적으로, 다음 순열을 찾는다는 것은 이 수보다 최소한으로 더 큰 수의 나열을 찾는다는 것이라고 할 수 있다.

예를 들어 n이 5이고, 주어진 순열이 (2, 5, 1, 4, 3) 이라고 해보자.

이 순열의 다음 순열을 찾는 방법은 1, 2, 3, 4, 5의 숫자들로 만들 수 있는 수들 중 25143 다음으로 큰 수를 찾는 방법과 같다는 것이다.

그렇다면, 25143 다음으로 큰 수를 만드는 알고리즘은 무엇일까?

우선, 바꿀 수 있는 가장 낮은 자릿수 i를 찾아야 한다. 우리가 원하는 것은 '최대한 조금 커지는 것'이기 때문에, 아래 자릿수의 값들 중 더 큰 값이 있는 자릿수 중에서 가장 낮은 자릿수를 찾아야 한다. 이 경우에는 백의 자릿수에 있는 1이다.

그리고 나서, 아래 자릿수들 중 i보다 크되, 가장 작은 자릿수 j를 찾아야 한다. 이 경우에는 일의 자릿수의 3에 해당한다.

마지막으로 두 수의 위치를 바꾸고, i보다 낮은 자릿수들을 정렬해야 한다. 당장 1과 3을 바꾸면 25341이 되겠지만 이는 25143 바로 다음의 수가 아니다. 25314를 만들 수 있기 때문이다.

 

위의 알고리즘을 코드로 나타내면 다음과 같다.

 

n = int(input())
target = list(map(int, input().split()))
i = n - 2

while 0 <= i:
    if target[i] < target[i + 1]:
        break
    else:
        i -= 1

if i == -1:
    print(-1)
else:
    j = n - 1
    while i < j:
        if target[i] < target[j]:
            target[i], target[j] = target[j], target[i]
            print(' '.join(map(str, (target[:i + 1] + sorted(target[i + 1:])))))
            break
        else:
            j -= 1