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

문제📖

풀이🙏

• 1 4 3 2를 예시로 알고리즘을 알아본다.

1. 뒤에서 부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고 (1,4)가 해당된다
   이 때, 1의 인덱스는 x, 4의 인덱스는 y라고 한다.
2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
   1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap 한다.
3. y에 해당하는 인덱스부터 오름차순 정렬을 한 뒤에 이어 붙인다.
   4 3 1을 sort 해서 1 3 4가 된다.
   이어 붙여 2 1 3 4가 된다.

코드💻

n = int(input())
data = list(map(int, input().split()))

for i in range(n-1, 0, -1): # 맨 뒤 값부터 시작
    if data[i-1] < data[i]:
        for j in range(n-1, 0, -1): # 다시 맨 뒤 값부터 큰 값찾기
            if data[i-1] < data[j]:
                data[i-1], data[j] = data[j], data[i-1] # 둘 값을 swap
                data = data[:i] + sorted(data[i:])
                for i in data:
                    print(i, end=' ')
                exit()
print(-1)