728x90
반응형
https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
문제 해결
10972와 반대 문제
https://thought-process-ing.tistory.com/92
[python] 백준 10972 다음 순열
https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문
thought-process-ing.tistory.com
뒤에서 부터 주어진 순열을 봤을 때 처음으로 i-1번째 수가 i번째 수보다 작을 때 i-1번째 수를 기준으로 잡고 다시 뒤에서부터 순열을 보았을 때 처음으로 i-1번째 수보다 큰 j번째 수(i≤j)를 보고 i-1번째 수와 j번째 수를 바꾸고 i번째 수부터 n번째 수까지 큰 수부터 수를 나열하는 내림차순으로 리스트를 정렬해 이어 붙이면 된다.
(ex) 12543
5번째 수부터 봤을 때
4>3 이므로 pass,
5>4이므로 pass,
2<5이므로 2를 고정으로 잡고 다시 뒤에 수부터 봤을 때
2<3이므로 2와 3의 수의 위치를 바꾼다. → 13542
13542에서 13 + (542를 내림차순으로 정렬)→ 13542
답 13542
CODE
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
for i in range(n-1,0,-1):
if A[i-1] > A[i]:
for j in range(n-1,0,-1):
if A[i-1] > A[j]:
A[i-1], A[j] = A[j], A[i-1]
B = sorted(A[i:], reverse=True)
A = A[:i] + B
print(*A)
exit()
print(-1)
728x90
반응형
'알고리즘 > [python] 백준 BOJ' 카테고리의 다른 글
[python] 백준 10819 차이를 최대로 (0) | 2023.01.10 |
---|---|
[python] 백준 10974 모든 순열 (0) | 2023.01.09 |
[python] 백준 10972 다음 순열 (0) | 2023.01.07 |
[python] 백준 15666 N과 M (12) (0) | 2023.01.06 |
[python] 백준 15665 N과 M (11) (1) | 2023.01.06 |
댓글