백준 10973 이전 순열 Kotlin (prev_permutation)

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

10973번: 이전 순열

문제

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을 출력한다.

알고리즘 분류

• 수학
• 구현
• 조합론

풀이

2022.06.26 - [알고리즘 문제 풀이/백준] - 백준 10972 다음 순열 Kotlin (next_permutation)

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

다음 순열 문제에서 조금만 바꾸면 된다.

다음 순열을 먼저 보고 아래 풀이의 주석을 본다면 쉽게 이해할 수 있다.

추가로 풀어보면 좋은 문제는 ZOAC

 

코드

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 max = 0
            var maxIdx = 0
            //i 우측에 있는 것보다 i가 크다면 바꾸기
            for (j in i+1 until this.size) {
                //i 우측에 있는 것중 i보다 작으면서 가장 큰 값 찾고 swap
                if (this[i] > this[j]) {
                    if(max < this[j]){
                        max = this[j]
                        maxIdx = j
                    }
                }
            }
            //swap
            if(max!=0){
                this[i] = this[maxIdx].also { this[maxIdx] = this[i] }
                this.sortDescending(i+1, this.size)
                return@apply
            }
        }
        //i보다 작은 값이 없다 -> 순열의 가장 처음 (전체 오름차순)이므로 -1 출력
        write("-1")
        close()
        return@with
    }
    //output
    write(answer.joinToString(" "))
    close()
}