[백준 알고리즘] 10972번 Python 풀이

백준 10972번 문제

 

이 문제는 10819번 문제를 풀던 도중, 모든 순열을 반환하는 라이브러리 사용 외 직접 순열을 구하는 방법을 찾다가 접하게 되었다. 본 문제의 핵심은 '사전 순으로' 다음 순열을 찾아 내는 것인데, 이를 구현하는 방법으로 나리야나 판디타라는 수학자가 고안한 알고리즘이 이미 있다고 한다. 알고리즘을 처음 봤을 때는 어떤 의미인지 감이 잘 오지 않았는데, 직접 값을 넣어보면서 차츰 익숙해졌다.

알고리즘의 동작은 다음과 같다.
1) 배열 내에서 a[k] < a[k+1]을 만족시키는 최대 k 찾기
2) a[k] < a[m]을 만족시키는 최대 m 찾기
3) a[k], a[m]의 순서 변경
4) a[k] 이후의 값 오름차순 정렬

이 알고리즘을 적용하면 문제는 쉽게 풀린다.

import sys


def next_permutation(list_a):
    k = -1
    m = -1

    # 증가하는 마지막 부분을 가리키는 index k 찾기
    for i in range(len(list_a)-1):
        if list_a[i] < list_a[i+1]:
            k = i

    # 전체 내림차순일 경우, 반환
    if k == -1:
        return [-1]

    # index k 이후 부분 중 값이 k보다 크면서 가장 멀리 있는 index m 찾기
    for i in range(k, len(list_a)):
        if list_a[k] < list_a[i]:
            m = i

    # k와 m의 값 바꾸기
    list_a[k], list_a[m] = list_a[m], list_a[k]

    # k index 이후 오름차순 정렬
    list_a = list_a[:k+1] + sorted(list_a[k+1:])
    return list_a


# main
n = int(sys.stdin.readline())
permutation = list(map(int, sys.stdin.readline().split()))

# 반환 받은 다음 순열 리스트를 출력
for num in next_permutation(permutation):
    print(num, end=' ')
print()