백준: 10972 다음 순열

문제

10972번: 다음 순열

 

문제 풀이

 이 문제는 특정 순열이 주어 질 때 다음 순열을 찾는 문제이다. c++의 경우 stl에 next permuation이 있기에 쉽게 풀 수 있지만, 파이썬의 경우 직접 구현하여야 한다. 따라서 파이썬으로 풀게 되면 단순히 라이브러리를 사용하는 것이 아닌 어떤식으로 동작하는지 알 수 있다.

 예시의 경우 주어진 순열은 1, 2, 3, 4로 해당 순열의 다음 순열은 1, 2, 4, 3이다. 모든 순열을 나열하고 다음 순열을 찾는것은 비효율적이다. 따라서 그림과 같은 방식을 통해 보다 효율적으로 다음 순열을 찾을 수 있다.

1. 뒤에서 부터 시작하여, 값이 증가하는지 확인하여 i 값을 결정한다.

   • 예시에서는 값이 계속 증가하므로, 결정된 i 값은 3이다.
   • 증가하는 수가 한 번도 없다면, 다음 수열이 없는 경우이다.

2. 뒤에서 부터 시작하여 결정된 i 값 - 1 부터 순차적으로 큰 값이 있는지 확인한다.

3. i와 j 값이 결정된다면 해당 값들을 swap한다.

4. 마지막으로 i, j에 위치한 값들을 반전시킨다.

 어려운 알고리즘이 아니므로, 로직을 기억하고 작성할 수 있다면 다양한 문제를 해결 할 수 있다.

 

코드

from sys import stdin


def prev_permutation(lst):
    length = len(lst) - 1
    i, j, k = [length for _ in range(3)]

    while i > 0 and lst[i - 1] >= lst[i]:
        i -= 1

    if not i:
        return 0

    while lst[i - 1] >= lst[j]:
        j -= 1

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

    while i < k:
        lst[i], lst[k] = lst[k], lst[i]
        i += 1
        k -= 1
    return lst

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    ret = prev_permutation(nums)
    print(-1) if not ret else print(*nums)