[백준] 10973번 이전 순열 - Python / 알고리즘 기초 2/2 - 브루트 포스 - 순열

---

---

---

💡 문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

---

💭 접근

10972번 다음 순열 문제와 완전히 정 반대인 문제이다. 이 문제의 경우에도 입력의 최대가 10,000이기에 일반적인 순열 알고리즘으로 모든 순열을 추출해서 비교하는 것은 불가능하다. 이 문제 역시 순열이 변화하는 패턴을 찾는 문제이다.

ex)
2 1 3 4 5 -> 2 1 3 4 5 -> (swap) 1 2 3 4 5 -> (반전) 1 5 4 3 2
2 1 4 3 5 -> 2 1 4 3 5 -> (swap) 2 1 3 4 5 -> (반전) 2 1 3 5 4

1. 주어진 수열을 뒤에서부터 탐색하며 처음으로 숫자가 커지는 수를 target으로 설정한다.
   -> (2 1 3 4 5)
2. 이후, 다시 수열을 뒤에서부터 탐색하며 처음으로 target보다 작은 수와 자리를 바꾼다.
   -> (2 1 3 4 5) - (1 2 3 4 5)
3. 마지막으로 target과 바꾼 수보다 뒤에 있는 숫자들을 반전한다.
   -> (1 2 3 4 5) - (1 5 4 3 2)

---

📒 코드

import sys

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

for i in range(n - 1, 0, -1):
    if num[i - 1] > num[i]:
        target = i - 1
        break
else:
    print(-1)
    sys.exit()

for i in range(n - 1, 0, -1):
    if num[target] > num[i]:
        num[target], num[i] = num[i], num[target]
        ans = num[:target + 1] + num[target + 1:][::-1]
        print(*ans)
        break

---

💭 후기

10972번 다음 순열 문제에서 조금만 변형하면 되는 문제였기에 어렵지 않게 해결하였다.

---

🔗 문제 출처

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

---