[수학/브루트포스] 백준 10972 다음 순열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10972번: 다음 순열

 

 

 

2. 문제 풀이

 다음 순열을 구하는 문제입니다.

 

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 순열은 오름차순 순서로 나열되며, N이 3일 때의 순열은 위와 같습니다.

 

 

 

3. 코드

from itertools import permutations
import sys
input = sys.stdin.readline

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

# 순열 계산
permutation = list(permutations(range(1, n+1), n))

# 다음 순열 찾기
cnt = 0
for idx, i in enumerate(permutation):
    if i == tuple(perm):
        cnt = idx+1

# 출력
if cnt == len(permutation):
    print(-1)
else:
    print(" ".join(map(str, permutation[cnt])))

 맨 처음에는 그저 순열을 전부 구하고, 주어진 순열의 다음 순열을 출력했습니다. 날먹 위 방법은 모든 순열을 구해야하므로 시간도 많이 걸릴 뿐더러, 메모리 초과가 납니다. (브루트포스로 못 풀잖아...ㅜㅜ)

 그대신, 다음 순열의 규칙을 찾아야 합니다.

 

1 2 3 4 => 1 2 4 3
2 4 3 1 => 3 1 2 4

1) 뒤에서부터 뒷 값이 앞 값보다 큰 경우를 찾습니다.
 1 2 3 4
 2 4 3 1

2) 뒤에서부터 비교하며, 앞 값보다 큰 값이 있다면 교환합니다.
 1 2 3 4 => 1 2 4 3
 2 4 3 1 => 3 4 2 1

3) 뒷 값에 해당하는 인덱스부터 끝까지 오름차순 정렬합니다.
1 2 4 3 => 1 2 4 3
3 4 2 1 => 3 1 2 4

 오름차순 정렬이므로, 다음 순열은 큰 값 하나를 앞으로 옮긴 순열입니다. 하지만, 그 뒤는 오름차순 정렬이 되야 합니다.

 

import sys
input = sys.stdin.readline

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

# 맨 뒤부터 탐색
for i in range(n-1, 0, -1):
    # 뒷 값이 앞 값보다 크면
    if perm[i-1] < perm[i]:
        # 다시 뒤에서부터, 앞 값보다 큰 값이 있는지 탐색
        for j in range(n-1, 0, -1):
            # 뒷 값이 앞 값보다 크면
            if perm[i-1] < perm[j]:
                # 두 값을 swap
                perm[i-1], perm[j] = perm[j], perm[i-1]
                # 뒷 값의 인덱스부터 끝까지 오름차순 정렬 후 출력
                perm = perm[:i] + sorted(perm[i:])
                print(" ".join(map(str, perm)))
                exit()
# 만약 뒷 값이 앞 값보다 큰 경우가 없다면, 맨 마지막 순열이므로 -1
print(-1)