[백준/BOJ] 10972번: 다음 순열

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

해설

예를 들어 문제를 풀어나가보자.

[3, 1, 5, 4, 2] 이와 같은 순열이 있다고 하자.

 

뒤의 3개를 보면 5, 4, 2로 내림차순으로 끝나 있다.

이는 3, 1로 시작하는 순열 중 가장 마지막에 올 수열이다.

따라서 다음 순열은 1의 위치를 바꿔야 한다는 것이다.

 

1과 바꿀 수로는 1보다 큰 5, 4, 2 중 최솟값이 된다.

따라서 [3, 2, 5, 4, 1]와 같이 바꾼 후 내림차순인 5, 4, 1을 오름차순으로 바꿔주면 된다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList

lateinit var list: ArrayList<Int>
var n = 0

fun main() {
    n = readLine()!!.toInt()
    val st = StringTokenizer(readLine())
    list = ArrayList(n)
    for(i in 0 until n) list.add(st.nextToken().toInt())
    if(next()) {
        for(i in 0 until n) print("${list[i]} ")
    }
    else println("-1")
}

fun next(): Boolean {
    var idx1 = list.size - 1
    while(idx1 > 0 && list[idx1 - 1] >= list[idx1]) idx1--
    if(idx1 <= 0) return false

    var idx2 = list.size - 1
    while(list[idx2] < list[idx1-1]) idx2--
    swap(idx1-1, idx2)
    idx2 = list.size - 1
    while(idx1 < idx2) {
        swap(idx1, idx2)
        idx1++
        idx2--
    }
    return true
}

fun swap(a: Int, b: Int) {
    var temp = list[a]
    list[a] = list[b]
    list[b] = temp
}