[백준 14003번] 가장 긴 증가하는 부분 수열 5 - Kotlin

[백준 14003번] 가장 긴 증가하는 부분 수열 5 - Kotlin

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

---

문제

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다

---

입력

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

---

출력

• 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
• 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

---

풀이

private class Solution14003 {

    fun solution(
        n: Int,
        a: IntArray
    ): String {
        val indexDp = IntArray(n)
        val list = mutableListOf<Int>()

        list.add(Int.MIN_VALUE)

        for (i in 0 until n) {
            when {
                list[list.size - 1] < a[i] -> {
                    list.add(a[i])
                    indexDp[i] = list.size - 1
                }
                else -> {
                    var left = 0
                    var right = list.size - 1

                    while (left < right) {
                        val center = (left + right) / 2

                        when {
                            list[center] >= a[i] -> right = center
                            else -> left = center + 1
                        }
                    }

                    list[right] = a[i]
                    indexDp[i] = right
                }
            }
        }

        val stringBuilder = StringBuilder()
        val resultDeque = ArrayDeque<Int>()
        var index = list.size - 1
        stringBuilder.append("$index\n")

        for (i in n - 1 downTo 0) {
            if (index == indexDp[i]) {
                resultDeque.add(a[i])
                index -= 1
            }
        }

        while (resultDeque.isNotEmpty()) {
            stringBuilder.append("${resultDeque.removeLast()} ")
        }

        return stringBuilder.toString()
    }

}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val a = when (n) {
        1 -> IntArray(n) { br.readLine().toInt() }
        else -> br.readLine().split(" ").map(String::toInt).toIntArray()
    }

    val solution14003 = Solution14003()

    bw.append("${solution14003.solution(n, a)}\n")
    bw.flush()

    br.close()
    bw.close()
}