[백준] 다음 순열

출처:: www.acmicpc.net/problem/10972

분류:: dp

 

1. 문제 이해 및 해결과정

- 1 부터 n으로 이루어진 수  1) a[i] <a[i+1] 이 성립하는 인덱스 i의 최대값을 찾는다. 찾을 수 없다면 수열 a가 마지막항이다.  2) 인덱스 i보다 크고, a[i]보다 큰 것들 중 가장 먼 인덱스 j를 찾는다 3) a[i]와 a[j] 값을 교환한다  4) 인덱스 i이후 값들을 오름차순으로 정렬 ex) [ 3, 1, 4, 2]  1) 증가하는 마지막 인덱스를 찾음 a[1]=1 2) 1보다 큰 값중 가장 먼 인덱스는 4이다. a[4]=2 3) a[1]과 a[4]를 swap [3,2,4,1] 4) a[1] 다음의 숫자들을 오름차순으로 정렬한다 [3,2,1,4] ex) [ 1,2,3,4] 1) 증가하는 마지막 인덱스를 찾음 a[3]=3  2) 3보다 큰 값중 가장 먼 인덱스는 4이다. a[4]=4 3) a[3] 과 a[4] swap [1,2,4,3] 4) a[3] 다음의 숫자들을 오름차순으로 정렬한다. [1,2,4,3] ex) [5,4,3,2,1] 1) 증가하는 마지막 인덱스를 찾음 ,없음-> a가 마지막 수열이다.  이를 Narayana Pandita  lexicographic ordering,라고 함

출처 : https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

2. 풀이방법

  1.

#다음 순열
#https://www.acmicpc.net/problem/10972
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
def next_permutation(a):
    i=-1
    #1. a[i] < a[i+1] 을 만족하는 인덱스의 최대값 찾기
    for index in range(len(a)-1):
        if a[index]<a[index+1]:
            i=index #증가하는 마지막 인덱스를 찾는다.
    #1-1
    if i==-1: #증가하는 마지막 인덱스가 없다면
        return -1 #모두 감소하는 수열
    #2. 인덱스 i보다 크고, a[i]보다 큰 것들 중 가장 먼 인덱스 j찾기
    for index in range(i+1,len(a)):
        if a[index]>a[i]:
            j=index
    #3. a[i]와 a[j]교환
    a[i],a[j]=a[j],a[i]
    #4. 인덱스 i이후 값들을 오름차순으로 정렬
    a=(a[:i+1]+sorted(a[i+1:]))
    return a

res=next_permutation(a)
if res!=-1: #다음 수열이 있으면
    print(' '.join(map(str,res)))
else: #마지막 수열
    print(-1)

 

3. 오답원인

 

4. 알게된 점