[백준][KOTIN][10972] 다음 순열

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

10972번: 다음 순열

문제 풀이

다음 순열에 대한 규칙을 이해하고 있을 때 문제를 접근할 수 있다.

<다음 순열>

1. 주어진 순열(number)을 오른쪽에서 부터 탐색하여 number[i] > number[i - 1] 위치를 찾는다.

2. 1번에서 구한 위치를 기준으로 순열을 나눈다.

3. 왼쪽의 순열에서 가장 마지막 인텍스의 값(a)과 오른쪽 순열에서 오른쪽 부터 탐색하여 (a) 보다 큰 값의 인덱스(b)를 찾는다. 위의 그림에서 4가 해당 된다. (a)와 (b) 를 swap 한다.

4. 오른쪽 순열을 오름 차순으로 정렬한다.

5. 두 순열을 합한다.

코드

import java.io.*

fun main (args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val number = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    var index = -1

    // 주어진 수열을 오른쪽에서 부터 탐색하여 number[i] > number[i - 1] 인 구간을 찾는다.
    for (i in (N - 1) downTo 1 step 1) {
        if (number[i] > number[i - 1]) {
            index = i
            break
        }
    }

    if (index == -1) {
        println(index)
    } else {
        // index 를 기준으로 두 개의 순열로 나눈 뒤
        // 왼쪽 순열과 오른쪽 순열을 오른쪽 부터 탐색하여 오른쪽 순열의 값이 왼쪽보다 큰 것을 찾는다.
        for (i in (N - 1) downTo index step 1) {
            if (number[index - 1] < number[i]) {
                val temp = number[index - 1]
                number[index - 1] = number[i]
                number[i] = temp
                break
            }
        }

        val sortList = mutableListOf<Int>()
        for (i in index until N) {
            sortList.add(number[i])
        }

        sortList.sort()

        val result = StringBuilder()

        for (i in 0 until index) {
            result.append("${number[i]} ")
        }

        for (i in 0 until (N - index)) {
            result.append("${sortList[i]} ")
        }

        println(result.toString())
    }
}