2022.02.28 [백준] (python 파이썬) 다음 순열

 

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

10972번: 다음 순열

---

풀이

이 문제는 다음 수열을 출력하는 문제이다.

 

1 4 3 2의 경우

1. 뒤에서부터 순열을 비교, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (1, 4 가 해당)
2. 이때 1의 인덱스를 x라고 하고 4의 인덱스를 y라고 한다.
3. 다시 두 번째 for 문으로부터 탐색하여 인덱스 x값 즉 1 보다 큰 값이 있으면 그 값과 1을 바꿔준다. -> 여기서는 1과 2이 바뀜
4. y에 해당하는 인덱스부터 정렬해준 뒤 이어 붙여준다. -> 여기서는 4 3 1을 정렬해준 1 3 4가 이어붙어 2 1 3 4가 되게 된다.

n=int(input())
 
arr=list(map(int,input().split()))
check=True
for i in range(n-1,0,-1):
    if arr[i-1]<arr[i]:
        x,y=i-1,i
        for j in range(n-1,0,-1):
            if arr[j]>arr[x]:
                arr[j],arr[x]=arr[x],arr[j]
                check=False
                break
    if not check:
        arr= arr[:y]+sorted(arr[y:])
        print(*arr)
        break
if check:
    print(-1)