[백준10972] 다음 순열

문제

---

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

10972번: 다음 순열

 

생각의 흐름

---

1. 다음 순열을 어떻게 찾아낼까? (규칙성)
2. 일의 자리부터 시작하여 바로 앞의 수보다 큰지 작은지를 비교하여 판별한다.

깨달은 점

---

1. 사실 파이썬에는 이러한 기능을 구현해주는 permutations라는 아주 편리한 라이브러리가 있다...하지만, 구현을 해보는 데에 의의가 있으니^^

코드

---

def next_permutation(arr):

    n = len(arr)-1
    if n==0:
        return -1
    i = n
    while arr[i-1] > arr[i]:
        i -= 1
        if i == 0:
            return -1

    j = i-1
    diff = 10000
    position_to_switch = 0
    for k in range(i, n+1):
        if arr[k]-arr[j] > 0:
            diff = min(diff, arr[k]-arr[j])
    for m in range(i, n+1):
        if arr[m]==arr[j]+diff:
            position_to_switch = m
            break
    temp = arr[j]
    arr[j] = arr[position_to_switch]
    arr[position_to_switch] = temp
    temp_list = arr[j+1:]
    temp_list.sort()
    arr = arr[:j+1]
    arr = arr + temp_list
    return arr

if __name__=='__main__':

    num = int(input())
    arr = list(map(int, input().split()))
    result = next_permutation(arr)
    if result == -1:
        print(-1)
    else:
        for p in result:
            print(p, end=' ')