[백준/BOJ] 12015번: 가장 긴 증가하는 부분 수열 2

문제

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

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

해설

문제의 예시를 가지고 문제를 풀어보자.

10 20 10 30 20 50이 있다.

여기서 가장 긴 증가하는 부분 수열(LIS)은 {10, 20, 30, 50}이 된다.

이를 구하는 방법으론 dp를 사용하는 것이 가장 먼저 떠오를 것이다. 하지만 dp를 사용하게 되면 범위가 너무 커 시간 초과가 발생한다.

 

이를 이분 탐색을 통해 해결할 수 있다.

우선 makeLis라는 배열을 선언해놓겠다.

makeLis 배열의 첫 값은 입력받은 첫번째 값으로 선언한다.

즉 makeLis[0] = arr[0](입력받은 값을 저장할 배열을 arr이라 하자.)이 된다.

또한 LIS의 길이를 저장할 변수를 선언하고 첫 값이 들어가 있으므로 len = 1을 초기값으로 준다.

 

이제 다음 값으로 20이 들어온다.

20은 10보다 크므로 len을 1 증가시켜주고, makeLis[len-1] = 20이 된다.

 

다음으론 10이 들어온다.

10은 20보다 작다.

따라서 이분 탐색을 통해 이 값을 넣어줄 위치를 찾을 것이다.

 

이분 탐색을 진행하기 위해 low, high 변수를 선언하고 초기값으로 각각 0과 len을 주었다.

이제 low < high을 만족할 때동안 반복을 하며 mid값인 (low + high) / 2를 구한다.

 

makeLis[mid]가 다음 값보다 작다면 low의 값이 mid + 1이 될 것이고

크거나 같다면 high의 값이 mid가 된다.

 

low가 high보다 커졌다면 makeLis[mid] = 다음 값(10)으로 초기화해주면 된다.

이 과정이 끝나면 가장 긴 증가하는 부분 순열이 완성된다.

코드

import java.util.*

private lateinit var arr: IntArray
private lateinit var makeLis: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    arr = IntArray(n)
    makeLis = IntArray(n)

    val st = StringTokenizer(readLine())
    repeat(n) { i -> arr[i] = st.nextToken().toInt() }

    lis(n)
}

private fun lis(n: Int) {
    makeLis[0] = arr[0]
    var len = 1

    for(i in 1 until n) {
        val next = arr[i]

        if(next > makeLis[len - 1]) {
            makeLis[len] = next
            len++
        }
        else {
            var low = 0
            var high = len

            while(low < high) {
                val mid = (low + high) / 2

                if(makeLis[mid] < next) low = mid + 1
                else high = mid
            }

            makeLis[low] = next
        }
    }

    println(len)
}