https://www.acmicpc.net/problem/10972
10972번: 다음 순열첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.www.acmicpc.net
실버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)솔직히 아직도 잘 모르겠다.
다음에다시풀어봐야겠다.