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

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

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

문제 풀이

1. 입력의 개수가 10,000 이하일 경우에는 완전 탐색을 이용하여 LIS 길이를 구한다.

2. 10,000 를 넘을 경우에는 이분 탐색을 이용해서 LIS 를 구해야 한다.

3. LIS 값을 저장하는 seq 배열을 선언하고 초기 값을 Int.MIN_VALUE 로 채운다.

4. A[i] 값이 seq[last index] 값보다 클 경우 seq 에 A[i] 를 저장한다.

5. A[i] 값이 seq[last index] 값보다 크지 않을 경우 A[i] 값을 넣을 targetIndex 를 이분 탐색을 이용하여 찾는다.

6. seq 값의 크기 - 1 의 값을 결과로 출력한다. 초기 값에 Int.MIN_VALUE 를 넣었기 때문에 1 작은 크기를 결과로 출력 한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val A = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    val seq = mutableListOf(Int.MIN_VALUE)
    // N 이 1,000,000 까지 이므로
    // 완전 탐색을 할 경우 시간 초과가 발생하기 때문에
    // 이분 탐색을 이용하여 LIS 길이를 구한다.
    for (i in 0 until N) {
        // A[i] 가 seq[index] 보다 크면 index + 1 을 index 로 가지는 seq 에 넣는다.
        if (A[i] > seq.last()) {
            seq.add(A[i])
        } else {
            // A[i] 가 seq[index] 보다 크지 않으면 현재 A[i] 값을 seq 의 어느 index 에 넣는 지 찾는다.
            val targetIndex = binarySearch(seq, A[i])
            //println("i = $i, ${A[i]}, $targetIndex")
            seq[targetIndex] = A[i]
        }
    }

    println(seq.size - 1)
}

private fun binarySearch(arr: MutableList<Int>, target: Int): Int {
    var start = 0
    var end = arr.size - 1

    while (start <= end) {
        val mid = (start + end) / 2
        if (arr[mid] > target) end = mid - 1
        else if (arr[mid] < target) start = mid + 1
        else return mid
    }

    return start
}