몰?.루();
백준 1722 코틀린 본문
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로 모든 순열을 구하는 방식으로 하면 메모리 초과 혹은 시간 초과가 나더라구요.
모든 순열을 구할 필요 없이 원하는 순열이 몇 번째인지만 구하면 되기 때문에 수학적으로 계산하면 되는 문제였습니다.
'프로그래밍 > 안드로이드, 코틀린' 카테고리의 다른 글
안드로이드 코틀린 미로 생성 알고리즘 (Randomized Prim's algorithm) (0) | 2022.11.09 |
---|---|
백준 1182 코틀린 (0) | 2022.11.04 |
백준 15683번 코틀린 (0) | 2022.10.28 |
백준 1074 코틀린 (0) | 2022.10.06 |
백준 1715 코틀린 (0) | 2022.09.29 |
Comments