[python] 백준 10973번 이전 순열

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

10973번: 이전 순열

 

 

 

💻 코드

 

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

for i in range(n - 1, 0, -1):
    if array[i - 1] > array[i]:
        for j in range(n - 1, 0, -1):
            if array[i - 1] > array[j]:
                array[i - 1], array[j] = array[j], array[i - 1]
                array = array[:i] + list(reversed(array[i:]))
                print(*array)
                exit()

print(-1)

 

 

 

📝 풀이

 

이 문제는 이전에 풀었던 백준 10972번 다음 순열 문제와 거의 비슷한 문제이다.

 

2022.07.27 - [Algorithm 문제 풀이/python] - [python] 백준 10972번 다음 순열

[python] 백준 10972번 다음 순열

 

 

 

입력한 순열에서 인덱스를 거꾸로 한 칸씩 비교하면서 필요한 부분을 교환하는 방식이다.

 

 

코드 설명

 

입력 예시) n = 3, array = 2 1 3

 

 

for i in range(n - 1, 0, -1):

 

i는 2부터 0까지(n - 1 ~ 0) 거꾸로 한 칸씩 이동하며 아래의 코드를 반복한다.

 

 

 

 

i가 2일 때,

 

if array[i - 1] > array[i]:

 

만약 array[1] > array[2]이라면 if문을 실행하도록 한다. 그런데 1 > 3이므로 if문을 실행하지 않는다.

 

 

 

i가 1일 때,

 

만약 array[0]  > array[1]이라면 if문을 실행하도록 한다. 2 > 1이므로 if문을 실행한다.

 

 

 

 

for j in range(n - 1, 0, -1):

 

j는 2부터 0까지(n - 1 ~ 0) 거꾸로 한 칸씩 이동하며 아래의 코드를 반복한다.

 

 

 

 

if array[i - 1] > array[j]:

 

i는 1이고, j는 2일 때,

 

만약 array[0] > array[2]이라면 if문을 실행하도록 한다. 2 > 3이므로 if문을 실행하지 않는다.

 

 

 

i는 1이고, j도 1일 때,

 

만약 array[0] > array[1]이라면 if문을 실행하도록 한다. 2 > 1이므로 if문을 실행한다.

 

 

 

 

array[i - 1], array[j] = array[j], array[i - 1]

 

array[0]과 array[1]의 값을 바꿔준다.

 

 

array = [2 1 3] ➡ array = [1 2 3]

 

 

 

 

array = array[:i] + list(reversed(array[i:]))

 

i를 기준으로 인덱스 i의 앞에 있는 값들은 그대로 정렬하고 인덱스 i의 뒤에 있는 값들은 거꾸로 정렬을 해준다.

 

 

array = [1 2 3] ➡ array = [1 3 2]