백준 알고리즘 문제풀이 10972(다음 순열) with 파이썬

문제설명

• 1부터 N까지 수로 이루어진 순열들이 있다.
• 순열이 주어지고 사전순으로 다음에 오는 순열을 구하는 것이다.

문제풀이

• C++ 에서는 next_permutation 함수를 통해서 다음 순열을 구할 수 있지만 Python에서는 제공해주지 않기 때문에 따로 구현해야한다. (라고 구글링을 통해 알았다...)
• 원리는 이렇다.

  예시로 [1,4,3,2] 순열이 있을때
  뒤에서부터 i라고 인덱스를 지정했을 때 i-1이 i보다 작은 경우를 찾는다.
  위에 예시에서는 (1,4) 조합이 해당된다.
  이때 i-1인덱스를 x로 i인덱스를 y로 저장한다.
  이후 다시 뒤에서 부터 x값보다 큰 값을 찾고 발견했을 때 x와 swap해준다.
  이후에는 y인덱스부터는 정렬을 하고 연결해준다.

  원리가 이렇다고 한다. 나도 처음 보는 거라 당황스럽기도 하고 새로운 사실을 알게 되서 좋았다.

문제 코드

n = int(input())
arr = list(map(int,input().split()))
chk = False
for i in range(n-1,0,-1):
  if arr[i-1] < arr[i]: ## 앞에 숫자가 뒤에숫자보다 작을 경우에
    for j in range(n-1,0,-1):
      if arr[j] > arr[i-1]:
        arr[j],arr[i-1] = arr[i-1],arr[j] ## swap바로 하기
        arr = arr[:i]+sorted(arr[i:])
        chk = True
        break
    if chk:
      print(*arr) ## 리스트 앞에 *을 붙일경우 1 2 3 4처럼 출력이 가능
      break
if chk == False:
  print(-1)