[백준] 10972번 다음 순열 - 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을 출력한다.

---

💭 접근

일반적인 순열 알고리즘의 경우 시간복잡도는 O(N!)이기 때문에 최대 입력이 10,000인 이 문제에서는 다른 방법을 사용해야한다.

우선 순열이 변화하는 패턴을 찾는다면 이 문제를 해결할 수 있는데,

ex)
1 5 4 3 2 -> 1 5 4 3 2 -> (swap) 2 5 4 3 1 -> (정렬) 2 1 3 4 5
2 1 3 5 4 -> 2 1 3 5 4 -> (swap) 2 1 4 5 3 -> (정렬) 2 1 4 3 5

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

---

📒 코드

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] + sorted(num[target + 1:])
        print(*ans)
        break

---

💭 후기

순열이 변화하는 패턴을 찾는게 까다로웠던 문제.

---

🔗 문제 출처

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

---