백준 알고리즘
[백준/Python]10972_다음 순열
헝그리개발자
2021. 6. 17. 14:57
문제
https://www.acmicpc.net/problem/10972
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
풀이
next_permutation 알고리즘을 사용합니다.
아래 페이지를 참고하세요.
https://steadycode.tistory.com/27
[알고리즘]Next Permutation 알고리즘
Next Permutation Algorithm은 순열 알고리즘 중에 하나로 무작위 순열의 다음 순열을 구하는 알고리즘입니다. 시간 복잡도는 O(N)이고 Greedy 알고리즘을 기반으로 합니다. 아래의 수열을 예로 다음에 올
steadycode.tistory.com
코드
import sys
def next_permutation(lst):
l = len(lst)
x = -1 # highest index
for i in range(l - 2, -1, -1):
if lst[i] < lst[i + 1]:
x = i
break
if x == -1:
return -1 # 다음 순열이 없다는 것을 의미
for j in range(l - 1, 0, -1):
if lst[j] > lst[x]:
lst[x], lst[j] = lst[j], lst[x]
break
return lst[:x + 1] + lst[:x:-1]
n = int(sys.stdin.readline().rstrip())
s = list(map(int, sys.stdin.readline().rstrip().split()))
answer = next_permutation(s)
if answer == -1:
print(answer)
exit(0)
print(*answer) # positional argument