몰?.루();

백준 1722 코틀린 본문

프로그래밍/안드로이드, 코틀린

백준 1722 코틀린

toonraon 2022. 10. 31. 21:08
fun main() {
    val n = readln().toInt()
    val inputs = readln().split(" ").map { it.toLong() }

    val arr = ArrayList<Int>()
    for (i in 1 .. n) arr.add(i)

    if (inputs[0] == 1L) {
        val answer = IntArray(n)
        solve1(arr, inputs[1], 0, answer)
        answer.forEach { print("$it ") }
    } else {
        val target = inputs.subList(1, inputs.size).map { it.toInt() }.toIntArray()
        println(solve2(arr, target, 0, 1))
    }
}

fun solve1(arr: ArrayList<Int>, k: Long, depth: Int, answer: IntArray): IntArray {
    if (arr.size == 0) {
        return answer
    }

    val fac = factorial(arr.size - 1)
    val a = ((k - 1) / fac).toInt()

    answer[depth] = arr[a]
    arr.removeAt(a)
    return solve1(arr, k - (a * fac), depth + 1, answer)
}

fun solve2(arr: ArrayList<Int>, target: IntArray, depth: Int, answer: Long): Long {
    if (arr.size == 0) {
        return answer
    }

    val fac = factorial(arr.size - 1)
    val a = arr.indexOf(target[depth])
    arr.remove(target[depth])

    return solve2(arr, target, depth + 1, answer + (a * fac))
}

fun factorial(n: Int): Long {
    var result = 1L
    for (i in 1 .. n) {
        result *= i
    }
    return result
}

처음엔 단순히 dfs로 모든 순열을 구해서 원하는 순열이 몇 번째 순열인지를 출력하게 했더니 메모리 초과가 났습니다.

알고보니 n이 20까지도 들어올 수 있어서 dfs로 모든 순열을 구하는 방식으로 하면 메모리 초과 혹은 시간 초과가 나더라구요.

모든 순열을 구할 필요 없이 원하는 순열이 몇 번째인지만 구하면 되기 때문에 수학적으로 계산하면 되는 문제였습니다.

Comments