알고리즘 - BOJ 10972 다음 순열 - Sat, Sep 5, 2020
다음 순열을 구하려면 브루트 포스
BOJ
BOJ 10972 다음 순열 문제는 말 그대로 사전순으로 다음 순열을 찾는 문제다.
일종의 Brute force 문제인데, 구현이 쉽지 않았다.
아이디어
단계 1
- 역순 정렬되어 있으면 다음 순열이 없으므로 -1 을 출력한다.
- 처음 바꿔야 하는 숫자를 뒤에서 앞으로 순회하며 찾는다.
- 대상은 자신의 값이 뒷자리보다 작은 숫자
- 예1: 1, 2, 3, [4], 5 라면 4가 해당
- 예2: 1, [2], 5, 4, 3 이라면 2가 해당
단계 2
- 이번에는 찾은 숫자 a와 바꿀 숫자 b를 다시 뒤에서부터 찾는다.
- 바꿀 숫자b는 처음으로 나오는 a보다 큰 수 이다.
- 예1: 1, 2, 3, [4], [5] 라면 a = 4, b = 5
- 예2: 1, [2], 5, 4, [3] 이라면 a = 2, b = 3
- 예3: 1, [3], 5, [4], 2 이라면 a = 3, b = 4
- 찾은 두 수 a, b를 스왑한다.
- 예1: 1, 2, 3, [4], [5] 라면 1, 2, 3, [5], [4]
- 예2: 1, [2], 5, 4, [3] 이라면 1, [3], 5, 4, [2]
- 예3: 1, [3], 5, [4], 2 이라면 1, [4], 5, [3], 2
단계 3
- 이 부분은 사실 이유는 모르지만 그렇데 된다는 것을 풀다가 알았다.
- 단계 2를 마치고 나면 a의 뒷자리는 항상 가장 큰 수가 된다.
- 그래서 a의 뒷자리를 뒤집어 주면 된다.
- 1, 2, 3, 4, 5 -> 1, 2, 3, 5, 4 (완성)
- 1, 2, 5, 4, 3 -> 1, 3, [5, 4, 2] -> 1, 3, [2, 4, 5]
- 1, 3, 5, 4, 2 -> 1, 4, [5, 3, 2] -> 1, 4, [2, 3, 5]
코드
import sys
n = int(input())
a = list(map(int, input().split()))
for i in range(n - 2, -1, -1):
if a[i] < a[i + 1]:
break
else:
print(-1)
sys.exit(0)
j = n - 1
while a[i] >= a[j]:
j -= 1
a[i], a[j] = a[j], a[i]
i += 1
j = n - 1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
print(" ".join(map(str, a)))
난이도
3점. 개인적으로 어려웠다. BOJ 난이도는 실버 3. 쉬운 편