백준 10973번 파이썬 문제풀이(브루트 포스 - 모든 순열)

코드

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:],reverse=True)
                print(*input_array)
                exit()
print(-1)

-> 10972 번 문제와 역으로 생각하면 쉬운 문제이다.

10972에서의 다음 순열은 우선 리스트에서 뒤에 값보다 앞의 값이 작은 애(x)를 찾고 그작은애를 기준으로 다시 리스트의 맨뒤 값부터 그 작은애(x)보다 큰값이 있는지 체크한다. 있다면 그 값과 작은애(x)를 스왑한 후 그 작은애를 기준으로 리스트를 절반으로 나누어 뒤에 값을 오름차순으로 정렬한 채로 다시 새로운 리스트를 만든다. 

 

위 문제는 10972의 과정을 반대로 생각한 것이다.  이전 순열은 우선 리스트에서 뒤에 값보다 앞의 값이 큰 애(y)를 찾고 그 큰애를 기준으로 다시 리스트의 맨뒤 값부터 그 큰애(y)보다 작은 값이 있는지 체크 한다. 있다면 그 값과 큰애(y)를 스왑한 후 그 큰애를 기준으로 리스트를 절반으로 나누어 뒤에 값을 내림차순으로 정렬한 채로 다시 새로운 리스트를 만든다. 

 

이해가 잘되지 않는다면 https://ji-gwang.tistory.com/262 (10972문제) 를 보고오자