[백준10972번] 다음 순열 / 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 4 3

예제 입력 2

5
5 4 3 2 1

예제 출력 2

-1

나의 풀이

이 문제를 풀기 위해서는 사전식 순열에서 다음 번 순열을 찾는 알고리즘을 알아야한다. 이 알고리즘은 14세기에 인도의 수학자 나라야나 판디타가 고안한 것이라고 한다. 이 알고리즘은 처음보면 무슨 소리인가 할 수도 있지만 잘 읽고 따져보고 한번 이해만 하면 쉽게 체득할 수 있을 것 같다.

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

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

이 순서를 거치고나면 바로 다음의 순열을 구할 수 있게된다. 예를들어보자.

a = [3,5,6,4,2,1]의 다음 사전식으로 오는 순열을 구해보자. (정답은 [3,6,1,2,4,5])

1. a 배열에서 a[k] < a[k+1]이 성립되는 k는 0과 1이다. 여기서 최댓값을 구해야되니 k는 1이 된다.
2. a[1] = 5 이다. 인덱스가 1이후에서 5보다 큰 수는 6뿐이니 m은 2가 된다.
3. a[k]와 a[m]의 값을 서로 바꾸어준다. => a = [3,6,5,4,2,1]
4. k이후의 값들을 오름차순으로 정렬한다. => a = [3,6,1,2,4,5]

알고리즘을 이해했다면 코드를 짜는 것은 수월할 것이다. 아래 코드를 참조하자.

코드

# 10972번 다음 순열
import sys

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

k = -1
# 1. k의 최댓값 구하기
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[k] < seq[j]:
            m = j

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

    # 4. k 이후 정렬
    tmp = seq[k+1:]
    tmp.sort()
    answer = seq[:k+1] + tmp

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