다음 순열

다음 순열

풀이

1. [2, 3, 6, 5, 4, 1]라는 순열이 있을 때, 오른쪽 끝에서부터 순회하여, 내림차순 배열이 끝나는 지점을 찾는다.
   
   2,3/6,5,4,1 => 2,3과 6,5,4,1사이에서 내림차순 배열이 끝이난다.

2. 교체할 자리를 찾는다.
   
   앞서 내림차순이 종료되는 숫자 (3)을 찾았다. 숫자3과 교체할 수를 찾는데 순열의 오른쪽 끝부터 시작하여 숫자(3)보다 큰 값을 찾는다.

3. 1, 2에서 찾은 두수를 교환한다.
   

4. 순열 [2, 4, 6, 5, 3, 1]에서 2 4를 고정시켰을 때 6 5 3 1은 가장 마지막에 올 수 있는 숫자 조합이다. 가장 처음으로 올 수 있는 숫자 조합이 되기 위해서는 6 5 3 1의 순서를 뒤집어야 한다.
   

코드

for test_case in range(1):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    flg = False
    for i in range(n-1, 0, -1):
        if arr[i] > arr[i-1]:
            target = arr[i-1]

            for j in range(n-1, i-1, -1):
                if target < arr[j]:
                    arr[i-1] = arr[j]
                    arr[j] = target
                    break

            ans = arr[:i] + sorted(arr[i:])
            print(' '.join(map(str, ans)))
            flg = True
            break

    if not flg:
        print(-1)

참고문서

https://passwd.tistory.com/entry/BOJ-10972-%EB%8B%A4%EC%9D%8C-%EC%88%9C%EC%97%B4next-permutation
https://otee.dev/2021/10/27/next-permutation.html