[백준] 10972번 다음 순열 ★

💡문제접근

• next_permutation 사전순으로 다음에 오는 순열을 구하는 알고리즘이다. 역량 테스트에서 자주 나오는 부분이므로 로직을 짜는 방법을 알아두는 것이 좋을 듯하다. 사전순으로 정렬하였을때, 앞부분의 수가 뒷부분의 수보다 커야 사전순으로 정렬이 수행된 것이라고 할 수 있다.

• 1 4 3 2를 예시로 알고리즘을 살펴보자.
  ①. 뒤에서부터 순열을 비교하며, 뒷부분의 값이 앞부분의 값보다 크다면 조건문을 수행한다. 사전순으로 정렬을 수행하게 된다면 당연히 앞부분의 값이 뒷부분의 값보다 커야 하므로 이와 반대인 경우 즉, 앞부분의 값이 뒷부분의 값보다 작은 경우 swap을 수행한다.
  (3 > 2)(x), (4 > 3)(x), (1 < 4)(o)이므로 1의 인덱스는 x, 4의 인덱스를 y라고 한다.
  ②. 다시 뒤에서부터 값을 비교하며 작은 값 1의 인덱스 x보다 큰 값이 있다면 그 값과 swap을 수행한다. 1과 2를 비교하고 2가 더 크므로 1과 2를 swap한다.
  ③. y에 해당하는 인덱스부터 오름차순 정렬을 한 뒤에 이어 붙인다.

next_permutation을 잘 몰라서 유튜브에 있는 구현 영상을 통해서 공부하면서 코드를 작성했다.

💡코드(메모리 : 31764KB, 시간 : 48ms)

import sys

N = int(input())
li = list(map(int, input().split()))

for i in range(N-1, 0, -1):
    if li[i-1] < li[i]:
        for j in range(N-1, 0, -1):
            if li[i-1] < li[j]:
                li[i-1], li[j] = li[j], li[i-1]
                li = li[:i] + sorted(li[i:])
                for i in li:
                    print(i, end = " ")
                sys.exit()
print(-1)

💡소요시간 : 41m