[백준][파이썬] 10972 다음순열

https://statssy.github.io/pro/2019/09/03/baekjoon_10972/를 참고했다.

[백준 문제] P10972 다음 순열(파이썬)

def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0: # 마지막 순열
        return False
    j = n
    while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
        j -= 1
    a[i-1], a[j] = a[j], a[i-1] # SWAP
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
        i += 1
        j -= 1
    return True

n = int(input())
a = list(map(int, input().split()))

if next_permutation(a) is True:
    for i in a:
        print(i, end=' ')
    print()
else:
    print(-1) # 마지막 순열

N과M 시리즈를 풀었지만, 이 문제를 못풀어서 뭔가 잘하고 있나? 라는 생각이 들었다.

하지만 N과M시리즈는 재귀함수에 대한 시야를 넓혀주었다면, 

이 문제는 순열이 만들어지는 논리과정을 수학적으로 생각 할 수 있도록 도와주는 문제이다.

 

살펴보면, 결국 함수안의 방식을 이해해야한다.

0. 숫자의 배열을 넘겨받는다

1. 오른쪽부터 있는 숫자를 두개씩 비교하여 큰 수가 왼쪽에 있을때 큰 수를 선택한다. ( - - - 큰수 작은수)

2. 그 큰수 왼쪽에 있는수( _ _ * 큰수 _) *보다는 오른쪽에 있는 수중 가장 큰수를 선택한다.

3. *과 큰수를 바꿔준다 (_ _ 큰수 * _)

4. 그리고 큰수 밑을 가장 작은 수로 정렬해준다.

 

사실 이해를 위해서는 코드를 보고 따라한다기보단, 원리를 직접 그려보고 코드를 짜는 연습을 해야할것 같다.

이해한것 같지만 아직 헷갈린다..