[백준10973번] 이전 순열 / Python3

문제

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을 출력한다.

예제 입력 1

4
1 2 3 4

예제 출력 1

-1

예제 입력 2

5
5 4 3 2 1

예제 출력 2

5 4 3 1 2

나의 풀이

10972번 다음 순열 문제와 알고리즘은 같다. 단지 비교나 정렬을 반대로만 해주면 된다.

알고리즘의 순서는 다음과 같다.

1. a[k] > a[k+1]가 성립하는 k의 최댓값을 찾는다. 
   - ( 만약 여기서 k값이 존재하지 않는다면 이미 오름차순으로 정렬이 되어있다는 뜻이다. )
2. 인덱스 k 이후의 값들 중 a[k] > a[m]이 성립하는 m의 최댓값을 찾는다.
3. k와 m 자리의 값을 서로 바꾸어 준다.
4. 인덱스 k 이후의 값들을 내림차순으로 정렬해준다.

코드

# 10973번 이전 순열
import sys

# main
n = int(input())
seq = [int(x) for x in sys.stdin.readline().split()]

# 1. k의 최댓값 찾기
k = -1
for i in range(len(seq)-1):
    if seq[i] > seq[i+1]:
        k = i

if k == -1:     # 오름차순인 경우
    print(-1)
else:
    # 2. m의 최댓값 구하기
    for j in range(k+1,len(seq)):
        if seq[j] < seq[k]:
            m = j

    # 3. k와 m의 값 바꿔치기
    seq[k], seq[m] = seq[m], seq[k]

    # 4. k이후의 값들 내림차순으로 정렬
    tmp = seq[k+1:]
    tmp.sort(reverse=True)
    answer = seq[:k+1] + tmp

    for num in answer:
        print(num, end= ' ')
    print()