[Python][백준 10972][알고리즘 - next permutation] 다음 순열 - 컴도리돌이

반응형

10972번: 다음 순열

 

문제 풀이에 도움 되었던 블로그

😊

[알고리즘] Next Permutation

---

문제 풀이

 

해당 문제는 permutation 알고리즘에 대해 알고 있으면 쉽게 문제를 해결할 수 있다.

 

c++에서는 알고리즘 라이브러리에서 next_permutation을 제공하고 있고, 

python에서는 itertools에서 permutations 라이브러리를 제공하고 있다.

 

해당 라이브러리들이 어떻게 작동하는지 이해하면 문제를 쉽게 해결할 수 있다.

 

하지만

 

필자가 이해시키는 것보다 더 나은 참고 자료를 위에 링크에 걸어두었다. 

🥲

 

next permutation 은 다음과 같이 구현할 수 있다.

 

1. arr[i-1] >= arr[i]가 되는 i 중에 제일 큰 값을 찾는다.

(여기서 i가 0이 되면 주어진 순열이 역순이라는 뜻이다. ex) 5, 4, 3, 2, 1)

 

2. arr[i-1] >= arr[j]가 되는 j 중 가장 큰 값을 찾는다.

 

3. arr[i] 와 arr[j]를 스왑 해준다.

 

4. arr의 i번째부터 끝까지의 원소를 뒤집는다.

 

---

def next_permutation() :
  i = j = k = n-1
  
  # 1. arr[i-1] >= arr[i]가 되는 i 중에 제일 큰 값을 찾는다.
  while i >0 and arr[i-1] >= arr[i]: i -= 1
  
  # i가 0이 되면 모든 값이 역순이라는 뜻 -1을 출력하고 return
  if i == 0 : print(-1) ; return
  
  # 2. arr[i-1] >= arr[j] 가 되는 j를 찾는다.
  while arr[i-1] >= arr[j] : j-=1
  
  # 3. i번째 값과 j번째 값을 스왑해준다.
  arr[i-1] , arr[j] = arr[j],arr[i-1]
  
  # 4. arr의 i번째부터 끝까지의 원소를 뒤집는다.
  while i < k :
    arr[i],arr[k] = arr[k],arr[i]
    i += 1; k -= 1
  print(*arr)

n,*arr= map(int,open(0).read().split()); next_permutation()