백준 10972 파이썬 - 다음 순열

 

10972번: 다음 순열

처음에 재귀를 통해 문제를 풀었지만 n의 범위가 10,000까지이기 때문에 런타임에러가 나왔다. n 범위를 항상 확인하고 빠르게 방법을 바꿨어야 했다,, ㅎㅎ 

다음으로 오는 순열을 알기 위해서는 아래와 같은 특정 규칙을 알아야 문제를 풀 수 있다.

풀이

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

1. 뒤에서 부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고 (1,4)가 해당된다.
    이 때, 1의 인덱스는 x, 4의 인덱스는 y라고 한다.

2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
    1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap 한다.

3. y에 해당하는 인덱스부터 오름차순 정렬을 한 뒤에 y이전 배열에 이어 붙인다.
    4 3 1을 sort 해서 1 3 4가 된다.이어 붙여 2 1 3 4가 된다.

 

코드

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

for i in range(n - 1, 0, -1):
    if arr[i] > arr[i - 1]:
        x = i - 1
        y = i
        for j in range(n - 1, 0, -1):
            if arr[x] < arr[j]:
                arr[x], arr[j] = arr[j], arr[x]
                new = arr[:y] + sorted(arr[y:])
                for val in new:
                    print(val, end=' ')
                exit()
print(-1)

참고

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