반응형
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
}
반응형
