[백준] 10972번: 다음 순열 / 파이썬

문제 링크

---

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

 

풀이 코드

---

n = int(input())
arr = list(map(int, input().split()))
x = [x for x in range(n,0,-1)]  # 마지막 순열

if arr == x:    # 마지막 순열일 경우 -1 출력 
    print(-1)

else:
    for i in range(n-1, 0, -1): # 뒤에서부터 비교
        if arr[i-1] < arr[i]:   # 작다면
            for j in range(n-1, 0, -1): # 뒤에서부터
                if arr[i-1] < arr[j]:   # 기준값과 비교
                    arr[i-1], arr[j] = arr[j], arr[i-1]  # 자리 교체
                    arr = arr[:i] + sorted(arr[i:]) # 뒤의 수 정렬
                    break
            break
    print(*arr) # 출력

코드 해석

---

 

1 4 3 5 2를 예로 들어보자.

1 4 3 5 2의 다음 순서는 1 4 5 2 3이 된다.

로직은 다음과 같다.

글씨 원래... 이것보다 예쁘다... 아이패드 적응중이라 이런거니 오해 말길...

 

 뒤에서부터 본인과 앞 수의 값을 비교한다.

만약 앞의 수(3)가 더 적다면

그 적은 수를 기준(3)으로 삼는다.

다시 뒤에서부터 기준보다 큰 값을 찾는다.

만약 큰 값(5)이 나온다면 서로 자리를 교체하고

뒤의 수를 오름차순으로 정렬한다.

 

 

로직 짜는 게 머리 아팠다.

체감 난이도: ★★★★☆