[백준/BOJ] 10973번: 이전 순열

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

해설

저번에 풀었던 https://jjunsu.tistory.com/122과 같은 유형의 문제이다.

 

[3, 4, 1, 2, 5]라는 순열이 있다 하자.

1, 2, 5를 보면 오름차순으로 되어있으므로 3, 4로 시작하는 순열 중 처음이라는 것을 알 수 있다.

따라서 4의 위치를 바꿔야 한다.

 

4와 바꿀 수는 1, 2, 5 중 4보다 작은 2가 와야 한다.

4와 2의 위치를 바꾸면 [3, 2, 1, 4, 5]가 되고 뒤의 1, 4, 5를 내림차순으로 정렬해주면 된다.

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

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

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

fun previous(): 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[idx1-1] < list[idx2]) 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
}