BOJ 10972 다음 순열

 

문제 링크 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

가장 마지막에 오는 것은 내림차순이라는 문제의 설명이 모든 것을 말해 주고 있다.

 

N=5 인 경우 즉, 1 2 3 4 5 로 이루어지는 한 순열을 관찰해 보자.

$$ 2 \; 3 \; 5 \; 4 \; 1 $$

 

1. 순열에서 가장 긴 내림차순으로 이루어진 마지막 부분(suffix)을 찾았을 때, 

앞 부분이 2  3 으로 시작되는 순열의 마지막임을 알게 된다.

그렇다면 앞 부분 2  3 을 바꾸어야 할 것이다.

 

2. 뒤의 5  4  1 중에서 3 보다 큰 첫 수를 찾아서 바꾸어야 한다.

 

3. 2의 결과 앞 부분은 2  3 에서 2  4 로 바뀌고 뒷 부분은 1  3  5 로 두고 새로이 순열을 구성한다.

 

위의 1, 2, 3 단계를 일반화시키면 문제는 해결된다.