[BOJ] 10972번 다음 순열

 

알고리즘 

 

예를 들어 입력 배열로 4 5 1 3 2 이 들어왔다고 하자

 

●  뒤에서부터, arr[i-1] < arr[i] 가 되는 i를 찾는다. i 는 3이 된다.

●  x를 i-1이라 하고, y를 i라고 하자. 그러면 x는 2, y는 3이다

●  뒤에서부터, arr[x] 보다 큰 값이 있으면, arr[x]와 swap하고, break한다. 그러면 배열은 4 5 2 3 1 이 된다.

●  y 이후의 배열에 대하여 정렬을 한다. 즉, arr = arr[:y] + sorted(arr[y:])

● 그러면 배열은 4 5 2 1 3 이 된다. 이것이 입력배열의 다음 순열이 된다. 

 

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

def f(arr):
    for i in range(N-1, 0, -1):
        if arr[i-1] < arr[i]:
            x = i-1
            y = i
            
            for j in range(N-1, y-1, -1):
                if arr[x] < arr[j]:
                    arr[x], arr[j] = arr[j], arr[x]
                    break
                    
            arr = arr[:y] + sorted(arr[y:])
            
            return arr
    
    return -1

arr = f(arr)
if arr == -1:
    print(arr)
else:
    print(*arr)