백준 10972 다음 순열

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

10972번: 다음 순열

실버3이지만 최근에 푼 문제중에 가장 어려웠다.

c++에서는 이를 함수하나로 쉽게 구할 수 있다한다.

도저희 모르겠어서 구글링했다.

 

알고리즘은 이렇다.

수열의 뒤에서부터, i >i-1인 경우를 찾는다.

i-1을 x, i-2를 y라 정하자

 

찾은 후, 다시 뒤에서부터 x보다 큰 값을 찾아 swap해준다.

이후, y전까지의 배열은 그대로 놔두고, [:i]

y부터 끝까지의 배열을 정렬한다. sorted([i:])

 

이 둘을 합치면 된다.

만일 i>i-1을 만족하는 i가 없다면, 이는 수열의 끝이다.

 

n=int(input())
arr=[* map(int,input().split())]

for i in range(n-1,0,-1):
    if arr[i]<arr[i-1]:continue

    if arr[i]>arr[i-1]:
        for j in range(n-1,0,-1):
            if arr[j]>arr[i-1]:
              
                arr[i-1],arr[j]=arr[j],arr[i-1]
                
             

                answer_arr=arr[:i]+sorted(arr[i:])
                print(* answer_arr)
                exit()
                
             

print(-1)

 

 

솔직히 아직도 잘 모르겠다.

다음에다시풀어봐야겠다.