[백준]10972번: 다음 순열 / 10973번: 이전 순열

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

10973번: 이전 순열

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

10972번: 다음 순열

이전 순열 찾기

예시 ) 2 3 1 4 5 의 이전 순열 찾기
 - 순열의 맨 끝(오른쪽)에서부터 순회하며 왼쪽 숫자가 오른쪽 숫자보다 처음으로 커지게 되는 부분을 찾는다.

    2 3 1 4 5

 - 큰 수를 뒤로 보내야 하기 때문에 큰 수와 자리 교환할 수를 탐색한다.

    예시에서 큰 수는 3이고, 우리는 이전 순열을 구해야 하기 때문에 3보다 작은 수를 교환해야 한다.

    따라서 순열의 맨 오른쪽에서부터 순회하며, 큰 수(예시에서는 3)보다 작은 수를 찾는다.

    2 3 1 4 5

 - 앞 단계에서 찾은 작은 수 1을 원래 3의 자리로 옮겨준다.

    2 1 3 4 5

 - 이제 순열의 2 1 까지 완성하였다.

    2 1 x x x 인 순열 중 가장 마지막 순열을 찾는 것이 최종 목표이므로, 나머지 오른쪽 부분을 내림차순으로 정렬해준다.

    2 1 5 4 3

---

python  코드

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int,input().split()))

if n==1:
  print(-1)
  exit()
  
# 순열의 맨 오른쪽부터, 왼쪽값 > 오른쪽값 만족하는 인덱스 찾기
idx = n
for i in range(n-1,0,-1):
  if data[i-1] > data[i]:
    idx = i-1
    break 
# 없으면 -1을 출력하고 종료
if idx == n:
  print(-1)
  exit()

# 자리교환하기
for i in range(n-1,idx,-1):
  if data[i] < data[idx]:
    data[i], data[idx] = data[idx], data[i]
    break

# 나머지 부분 내림차순 정렬 및 결과 출력
answer = data[:idx+1] + sorted(data[idx+1:],reverse=True)
for i in range(n-1):
  print(answer[i],end=' ')
print(answer[-1])

---

다음 순열 찾기

 - 이전 순열과 같은 원리이다. 적절히 등호만 바꾸어 작성하면 된다.