[백준] 12015번: 가장 긴 증가하는 부분 수열 2 - Kotlin[코틀린]

문제

 

12015번: 가장 긴 증가하는 부분 수열 2

 

---

풀이

 

 이 문제는  '11053번 가장 긴 증가하는 수열'  문제와 유사하지만 입력 범위가 크기 때문에 DP로 풀이하면 시간초과가 발생한다. 대신 LIS를 구하는 다른 방법인 이분 탐색을 활용해 풀이해야한다.

 

 우선 입력 받은 수열을 가장 긴 증가하는 수열로 만드는 방법을 확인해보자. 어느 수열의 첫 5개의 원소가 [30, 35, 40, 10, 20, ...]일 때 현재까지의 LIS는 [30, 35, 40]이 될 것이다. 여기서 이 LIS는 수열의 다음 원소들에 따라 의미가 있을 수도 있고 없을 수도 있다. 예를 들어 전체 수열이 [30, 35, 40, 10, 20, 15]인 경우에는 LIS가 [30, 35, 40]으로 찾으려던 답인 LIS가 된다. 하지만 전체 수열이 [30, 35, 40, 10, 20, 25, 30]인 경우에는 LIS가 [10, 20, 25, 30]이 되고, [30, 35, 40]은 의미없는 수열이 될 것이다. 그렇기 때문에 배열을 탐색하면서 LIS를 기록할 때 의미있는 정보가 어떤 것인지 알아야한다.

 

 [30, 35, 40, 10, 20, 25]에서 증가하는 부분 수열을 길이별로 나타내면 다음과 같다.

 

 - 길이 1: [30], [35], [40], [10], [20], [25]

 - 길이 2: [30, 35], [30, 40], [35, 40], [10, 20], [10, 25]

 - 길이 3: [30, 35, 40], [10, 20, 25]

 

 여기서 중요 정보는 각 길이별 부분 수열마다 마지막 원소 중 최솟값이다. 길이 1에서는 10, 길이 2에서는 20, 길이 3에서는 25이다. 만약 다음 원소의 값이 30일 때, 길이가 3인 부분 수열 중 [30, 35, 40]은 [30, 35, 40, 30]으로 LIS가 되지 못하고 [10, 20, 25]는 [10, 20, 25, 30]으로 길이가 4인 LIS가 된다. 그렇기 때문에 길이가 3인 부분수열에서 마지막 원소의 최솟값이 25인 것이 중요한 정보가 되는 것이다. 또한 길이가 4인 LIS에서 마지막 원소들 중 최솟값은 30이 된다.

 

 이 정보들을 기록하기 위해 필요한 것이 이분 탐색이다. 이분 탐색을 구현하기 위해 먼저 의미있는 정보를 기록할 리스트를 선언한다. 배열을 탐색하면서 리스트의 마지막 값보다 원소의 값이 크다면 리스트에 추가해준다. 그렇지 않다면 리스트의 중간부터 확인하면서 원소의 자리를 찾아 리스트에 대입해준다. 모든 탐색이 끝나면 리스트의 길이가 구하려는 LIS의 길이가 된다.

 

 [30, 35, 40, 10, 20, 25, 30]을 탐색하는 과정에서 리스트는 다음과 같이 변한다.

 - 30 입력 -> 30

 - 35 입력 -> 30, 35

 - 40 입력 -> 30, 35, 40

 - 10 입력 -> 10, 35, 40

 - 20 입력 -> 10, 20, 40

 - 25 입력 -> 10, 20, 25

 - 30 입력 -> 10, 20, 25, 30

 

자바의 Arrays.binarySearch() 메소드가 위와 같은 방식으로 구현되어 있어 이를 이용해 문제를 해결할 수도 있다.

 

---

코드

 

import java.util.*

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

    val num = br.readLine().toInt()
    val st = StringTokenizer(br.readLine())
    val arr = IntArray(num){ st.nextToken().toInt() }
    val list = mutableListOf<Int>()

    for(tmp in arr) {
        if(list.size == 0 || list.last()<tmp) {
            list.add(tmp)
        } else {
            var lo = 0
            var hi = list.size

            while(lo<hi) {
                val mid = (lo+hi)/2

                if(list[mid]<tmp) {
                    lo = mid + 1
                } else {
                    hi = mid
                }
            }
            list[lo] = tmp
            
            // 내장 함수 binarySearch() 활용
            /*
            val index = list.binarySearch(tmp)
            if (index < 0) {
                list[-index - 1] = tmp
            }
            */
        }
    }

    bw.write("${list.size}")
    bw.flush()
    bw.close()
    br.close()
}