알고리즘 - 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. 쉬운 편