백준 10972 다음 순열 Kotlin (next_permutation)

문제 출처 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

알고리즘 분류

• 수학
• 조합론

풀이

c++의 STL엔 있지만 Java에는 없어서 직접 구현해야 한다던 next_permutation

사실 이 문제를 풀기 전에

2022.06.10 - [알고리즘 문제 풀이/백준] - 백준 ZOAC 16719 Kotlin (구현)

이 문제를 먼저 풀었었는데,

next_permutation에 대한 개념이 없는 상태로 그냥 구현했다.

근데 구현하고 보니 next_permutation 알고리즘이더라.

?.?

이 문제를 풀다가 이게 next_permutation이구나 알았다.

 

next_permutation의 핵심은 다음과 같다.

1. 오른쪽부터 왼쪽으로 바꿀 위치 i를 찾는다.

2. 이때 i란 i의 오른쪽 요소들 중에 i보다 큰 값이 있는 경우 i가 성립된다.

3. i의 오른쪽에 i보다 큰 값이 있는 경우, 이 큰 값들 중 가장 작은 값을 찾아 swap한다.

4. i에는 i보다 큰 값 중 가장 작은 값이 들어와있다. 이제 i 오른쪽에 있는 요소들을 오름차순 정렬해 준다.

5. 5 4 3 2 1 같은 경우는 가장 마지막 순열인데, 주어진 배열에서 i를 찾지 못한 경우이다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    //solve
    val answer = getIntList().toIntArray().apply {
        //바꿀 위치 탐색
        for (i in this.size - 2 downTo 0) {
            var min = Int.MAX_VALUE
            var minIdx = 0
            //i 우측에 있는 것보다 i가 작다면 바꾸기
            for (j in i+1 until this.size) {
                //i 우측에 있는 것중 i보다 크면서 가장 작은 값 찾고 swap
                if (this[i] < this[j]) {
                    if(min > this[j]){
                        min = this[j]
                        minIdx = j
                    }
                }
            }
            //swap, i 이후의 값들은 오름차순 정렬
            if(min!=Int.MAX_VALUE){
                this[i] = this[minIdx].also { this[minIdx] = this[i] }
                this.sort(i + 1, this.size)
                return@apply
            }
        }
        //i보다 작은 값이 없다 -> 순열의 가장 마지막 (전체 내림차순)이므로 -1 출력
        write("-1")
        close()
        return@with
    }
    //output
    write(answer.joinToString(" "))
    close()
}