[백준]10972 다음순열

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

<문제 요약>

1. 0이 아닌 N수를 입력받음

2. 1~N까지의 수로 이루어진 순열 정렬(오름차순 ~ 내림차순)

3. 입력한 순열 다음 순서의 순열을 출력

 

 

 

N = int(input())  
array = list(map(int, input().split()))

if array == sorted(array,reverse = True):   # 입력된 순열이 맨 마지막 순서인 내림차순인 순열일 때
    print("-1")

 

 

else:
    n = 0
    for i in range(N-1,0,-1):  # 마지막 인덱스부터 첫번째 인덱스 순으로 
        if array[i-1] < array[i]:  # 앞의 숫자가 뒤의 숫자보다 작을 때
            n = i-1
            break  # 이 때 인덱스는 최대여야 한다.

    for j in range(N-1,0,-1):  # 마지막 인덱스부터 첫번째 인덱스 순으로
        if array[n] < array[j]:
            array[n], array[j] = array[j], array[n]  # 스왑
            array = array[:n+1] + sorted(array[n+1:])  # next permutation
            print(*array)  # 리스트를 순열형식으로 출력
            break

 

<접근>

1.순열의 뒷 인덱스부터 첫번째 인덱스 방향으로 갈 때 숫자의 크기가 작아지는 최대지점을 찾기(i)

2. i-1 지점에서 인덱스 수가 커지는 방향으로 갈 때 i-1번째 인덱스보다 큰 인덱스가 있는 최대지점을 찾기(j)

3. i-1번째 인덱스와 j번째 인덱스를 스왑

4. (0~i-1) 번째까지의 array + (i~끝까지)sorted된 array

5. 리스트를 순열형식으로 출력