[백준] 이전 수열

출처:: https://www.acmicpc.net/problem/10973

분류:: 브루트포스

 

1. 문제 이해 및 해결과정

- 다음 순열 문제(hiruby.tistory.com/521)와 알고리즘 유사 1) 감소하는 것들 중 가장 큰 인덱스 찾기    1-1) 감소하는 것들이 없다면, 가장 처음 오는 수열이 된다 2) 인덱스 i보다 큰 수 중 a[i]보다 더 작은 값 찾기 3) a[i]와 a[j] 값 swqp 4) i보다 큰 수들을 내림차순으로 배열

 

2. 풀이방법

 1. 

#이전순열
#https://www.acmicpc.net/problem/10973
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. 감소하는 것들중 가장 큰 인덱스 찾기
    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]보다 더 작은 값 찾기
    for index in range(i+1,len(a)):
        if a[index]<a[i]:
            j=index
    #3. a[i]와 a[j] swap
    a[i],a[j]=a[j],a[i]
    #4. i보다 큰 수들을 역순(내림차순) 으로 배열
    a=a[:i+1]+sorted(a[i+1:],reverse=True)
    return a

res=next_permutation(a)
if res==-1: #사전 순으로 가장 처음 오는 수열일 경우
    print(-1)
else:
    print(' '.join(map(str,res)))

 

3. 오답원인

 

4. 알게된 점