[BOJ 10972]

문제 바로가기 : https://www.acmicpc.net/problem/10972
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

1~N의 순서가 주어졌을 때 다음 순열을 구하는 문제다.
다음 순열로 넘어갈 때 바뀌는 자리는 최소 2자리이다. 많으면 통째로 바뀔 수도 있다.
그럼 언제 2자리가 바뀌고 언제는 통째로 바뀌는지 생각해 볼 필요가 있다.

순열에서는 뒤에서부터 가장 먼저 발견되는 내림차순인 구간이 있다면 구간의 시작 직전 위치까지 통째로 바뀌게 된다.
근데 그 구간의 범위에 따라 언제는 2자리만, 언제는 2자리보다 많이 바뀌는 것 처럼 보일 뿐이다.
기본적으로 적용되는 원리는 같다. 다음 예를 보자.

뒤에서부터 탐색해야 한다.
내림차순인 구간은 5번째밖에 없다.
때문에 4번째와 5번째를 스왑해준다.
    1 3 4 2 5
->  1 3 4 5 2

[4, 5]가 내림차순이다.
그럼 영향을 받는 구간은 [3, 5]가 된다.
그러나 [4, 5]에서 3번째 값보다 크면서 + 제일 작은 값이 와야 한다.
때문에 다음과 같이 바뀌게 된다.
    1 3 4 5 2
->  1 3 5 2 4

몇 번째부터 내림차순인지 파악하기 위해 isdesc()를 bool 타입으로 만들어줬다.
(N 범위가 작아서 앞에서부터 탐색하는 비효율적인 방법이다. 뒤에서부터 대소비교를 하면 O(N)만에 구할 수 있다)
i번째에서 isdesc()이 true이면 다음과 같은 과정을 거치고 break문을 통해 for문을 나와 출력한다.

i가 0이라면 모두 내림차순이라는 말이므로 마지막 순열인 상태이다. 때문에 -1을 출력한다.
그렇지 않다면 [i, n)에서 오름차순으로 정렬하고 i-1번째 값보다 크면서 [i, n)에서 가장 작은 값을 찾는다.
가장 작은 값의 인덱스를 idx라고 하면 i-1번과 idx번을 스왑해주고 출력한다.