[Kotlin] 99 클럽 코딩 테스트 스터디 미들러 29일차 - Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

[문제]

이 문제는 주어진 정수 배열 nums에서 "가장 긴 엄격히 증가하는 부분 수열(Longest Increasing Subsequence, LIS)"의 길이를 구하는 것입니다.

용어 설명

• 부분 수열(Subsequence): 주어진 배열에서 순서를 유지한 채 일부 원소들을 선택하여 만든 배열입니다. 예를 들어, 배열 [10, 9, 2, 5]의 부분 수열에는 [10, 9], [2, 5], [10, 5] 등이 있습니다.
• 엄격히 증가하는 부분 수열(Strictly Increasing Subsequence): 수열 내의 각 원소들이 이전 원소보다 큰 경우를 의미합니다. 예를 들어, [2, 3, 7, 101]은 엄격히 증가하는 수열입니다.

[입출력 예]

 

[풀이]

증가하는 부분 수열을 만들 수 있는 케이스 중에 가장 그 List의 길이 긴 경우의 size를 반환하면 됩니다.

fun lengthOfLIS(nums: IntArray): Int {
    if (nums.isEmpty()) return 0

    val sub = mutableListOf<Int>()

    for (num in nums) {
        var left = 0
        var right = sub.size

        while (left < right) {
            val mid = (left + right) / 2
            if (sub[mid] < num) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        // 만약 num이 sub의 모든 원소보다 크다면, sub 리스트에 추가합니다.
        // 그렇지 않다면, 적절한 위치에 값을 갱신합니다.
        if (left < sub.size) {
            sub[left] = num
        } else {
            sub.add(num)
        }
    }

    // 최종적으로 sub 리스트의 크기가 가장 긴 증가하는 부분 수열의 길이가 됩니다.
    return sub.size
}