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

백준 알고리즘 10974번

 

이 문제도 10972번 문제와 마찬가지로 10819번 문제를 풀던 도중 라이브러리 사용을 하지 않고 모든 순열 탐색을 구현하기 위해 방법을 찾던 도중 접해 풀게 되었다.

10972번과 굉장히 유사한데, 이 문제의 특징은 모든 순열을 출력하는 것이다. 결과적으로, 10972번에서 사용한 다음 순열 찾기 알고리즘을 적용하기 전에, 입력으로 받은 N을 오름차순으로 1...N 배열을 먼저 생성한다. 이후, 알고리즘을 구현한 함수에 이 배열을 넣어 재귀적으로 모든 구간에서 내림차순일 때까지 반복 호출하면 된다.

함수가 다음 순열을 구하는 기능이기 때문에, 사전순으로 첫 순열도 먼저 출력해주고 N이 1이 아니라면 다음 순열을 구해 출력하는 구조로 구현했다.

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

    # 전체 내림차순일 경우, 출력 후 -1 반환(break Flag)
    if k == -1:
        return -1

    # index k 이후 부분 중 값이 k보다 크면서 가장 멀리 있는 index m 찾기
    for i in range(k+1, 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


n = int(sys.stdin.readline())
arr = []
for i in range(1, n+1):
    arr.append(i)

# 사전순 첫 순열
for i in arr:
    print(i, end=' ')

# 다음 순열
if len(arr) != 1:
    print()
    result = arr
    while True:
        result = next_permutation(result)
        if result == -1:
            break

        for i in result:
            print(i, end=' ')
        print()