[Problem] 백준 10972번 다음 순열

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

10972번: 다음 순열

간단한 풀이

예를 들어, 1 7 6 5 4 3 2 라는 n번째 순열이 있을 때, 다음 n+1번째 순열은 2 1 3 4 5 6 7 이 된다.

 

그 과정을 잘 살펴보기위해 순열을 1 7 6 5 4 3 2 와 2 1 3 4 5 6 7, 파란부분 빨간부분 2가지 부분을 나눠보자.

1 7 6 5 4 3 2는 1로 시작하는 순열 중 가장 마지막, 가장 큰 순열이다. (내림차순)

2 1 3 4 5 6 7은 2로 시작하는 순열 중 가장 처음, 가장 작은 순열이다. (오름차순)

1 7 6 5 4 3 2 순열이 2 1 3 4 5 6 7 순열로 바뀌는, 다음 순열을 구하는 과정은 위와 같은 구조로 파악하면 쉽다.

 

다른 예로 2 3 1 7 6 5 4 의 다음 순열은 2 3 4 1 5 6 7 이 된다.

이 순열은 2 3 1로 시작하는 순열 중 가장 마지막 순열이 2 3 4로 시작하는 가장 처음 순열로 바뀐 것과 동일하다

2 3 1 7 6 5 4 => 2 3 4 1 5 6 7

 

---

간단한 수도코드

이걸 구하는 과정을 대충 표현하면 아래와 같다.

1. 뒤에서부터 내림차순이 시작되는 위치를 찾는다. (i+1번째부터 내림차순 시작)

2. A[i]와 바꿀 A[j]의 위치를 찾는다. (A[j]는 맨 뒤에서부터 시작해 A[i]보다 처음으로 큰 수)

3. A[i]와 A[j]를 서로 바꾼다.

4. A[i+1]부터 끝까지 순열을 뒤집는다.

수도코드로 표현하면 아래와 같다.

1. A[i - 1] < A[i] 를 만족하는 가장 큰 i를 찾는다.

2. j >= i 이면서 A[j] > A[i-1]을 만족시키는 가장 큰 j를 찾는다.

3. A[i-1]과 A[j]를 서로 바꾼다.

4. A[i]부터 순열을 뒤집는다.

---

알게된 점

다음순열/이전순열을 구하는 방법을 알게 되었다.

이전 순열은 다음 순열을 반대로만 구현하면 된다.