백준 10972번 파이썬 문제풀이(브루트 포스 - 다음 순열)

코드

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

for i in range(N - 1, 0, -1):  # 마지막 항부터 돈다
    if input_array[i - 1] < input_array[i]:  # 만약 앞 열의 값이 그 뒷열의 값보다 작다면
        for j in range(N - 1, 0, -1):  # 다시 그 앞 열의 값을 맨 뒷열부터 비교
            if input_array[i - 1] < input_array[j]:  # 그 앞열의 값이 뒤에 있는 어느 열보다 작다면
                input_array[i - 1], input_array[j] = input_array[j], input_array[i - 1]  # 그 두 값을 스왑
                input_array = input_array[:i] + sorted(input_array[i:])  # i-1 번째 까지의 리스트와 그 뒤에리스트를 정렬한 채로 붙인다.
                print(*input_array)  # *를 이용해 리스트 내부의 원소들을 공백을 사용하여 출력
                exit()  # 코드 종료

print(-1)  # 만약 위에서 코드 종료가 일어나지 않았다면(마지막 항이라면) -1 출력

-> 위 문제는 C++에서는 next_permutation을 사용하면 쉽게 풀 수 있지만 python에는 이 알고리즘을 직접 구현해서 풀어야 한다. 이러한 개념을 모르고 처음 접해보면 굉장히 어렵고 이 규칙을 찾기가 힘들 수도 있다. 한번쯤은 아는 것이 좋다. next_permutation은 위와 같은 알고리즘을 통해서 구한다. 처음에 위 문제를 재귀, 파이썬의 permutation으로 풀려고하니 시간초과 메모리초과등 초과란 초과는 다발생했다. 다음의 알고리즘을 이해해야하만 풀 수 있는 문제이다.

 

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

 

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