728x90
문제
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을 출력한다.
코드
# 10972
import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
x = 0
for i in range(n-1, 0, -1):
if arr[i] > arr[i-1]:
x = i-1
break
for i in range(n-1, 0, -1):
if arr[x] < arr[i]:
arr[x], arr[i] = arr[i], arr[x]
arr = arr[:x+1] + sorted(arr[x+1:])
print(*arr)
exit()
print(-1)
풀이
next_permutation
- 순열의 뒤 부터 비교하며 뒷 값이 앞 값 보다 큰 인덱스 구해서 x에 앞 값 인덱스 넣기
- 이 x 값과 다시 순열의 뒤부터 비교해서 arr[x] 보다 큰 값 구하고 swap 진행하기
- x 다음 값이 큰 값이었다.
- 이 값 기준으로 앞은 그대로, 뒤는 sorted 해서 포인트로 접근 print()
- exit() 종료
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
[백준] 17427 약수의 합 2 python (0) | 2022.03.31 |
---|---|
[백준] 1316 그룹 단어 체커 python (0) | 2022.03.29 |
[백준] 1476 날짜 계산 python (0) | 2022.03.26 |
[백준] 3085 사탕 게임 python( *) (0) | 2022.03.26 |
[백준] 11724 연결 요소의 개수 python (0) | 2022.03.26 |