[99클럽 코테 스터디 29일차 TIL] LeetCode - Longest Increasing Subsequence
99클럽 코테 스터디 29일차 TIL 입니다.
Medium
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
풀이 코드
class Solution {
public int lengthOfLIS(int[] nums) {
int[] len = new int[nums.length];
Arrays.fill(len, 1);
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) { // 나보다 작고
len[i] = Math.max(len[i], len[j] + 1); // 수열 길이 가장 큰 값 + 1
}
}
}
int max = 0;
for (int l : len) {
max = Math.max(max, l);
}
return max;
}
}Time: 36 ms
Space: 44.3 MB
해당 문제는 주어진 숫자 배열에서 가장 긴 증가 수열을 구하면 되는 문제다. 처음엔 수열을 공비수열로 생각해서 예시부터 왜 그렇게 나오는지 이해를 못했고 꽤 헤맸다.
어떻게 풀어야할지 처음 생각한 방식은 주어진 배열의 각 수가 가장 마지막 숫자일 때의 수열 크기를 담은 배열(len)을 만들고 그 중 가장 큰 값을 반환하는 것으로 생각했다. 이를 위해서 수를 뽑을 때 그 이전까지의 수 중에 작은 수가 있는지 확인한다. 여기까지만 생각하면 아래와 같은 문제가 생긴다.
input : [10, 9, 2, 5, 3, 7, 100]
len : [1, 1, 1, 2, 2, 4, 5]
expected : 4
output : 5
숫자 7 일 때의 수열은 [2, 3, 7] 로 길이는 3 이어야 하고 100 일 때는 [2, 3, 7, 100] 으로 길이가 4 여야 한다. 이 문제를 해결하기 위해 유심히 여러 케이스를 확인해보니 주어진 배열에서 뽑은 각 수가 마지막 숫자일 때의 가장 큰 증가 수열 크기는 이전까지의 뽑은 수 중 나보다 작으면서 가장 큰 증가 수열의 크기 + 1 인 것으로 확인했다. 예를 들어,
input : [10, 9, 2, 5, 3, 4, 100]
len : [10보다 작은 수 없음, 9보다 작은 수 없음, 2보다 작은 수 없음, 5보다 작은 2의 증가 수열의 크기 + 1, 3보다 작은 2의 증가 수열의 크기 + 1, 4보다 작은 2 와 3 중 증가 수열의 크기가 가장 큰 3의 증가 수열의 크기 + 1, 100보다 작은 2, 5, 3, 4 중 증가 수열의 크기가 가장 큰 4의 증가 수열의 크기 + 1]
-> len : [1, 1, 1, 1 + 1, 1 + 1, (1 + 1) + 1, ((1 + 1) + 1) + 1]
-> len : [1, 1, 1, 2, 2, 3, 4]
이해가 됐으면 좋겠습니다. 따라서 위 풀이 코드에 적혀 있는 주석의 조건식이 완성된다. 이 문제를 이분 탐색으로도 풀 수 있다고 한다. 아래 풀이는 클럽장님이 공유해주신 풀이로 풀이를 따라 예시 값을 넣다보면 이해가 된다.
이분 탐색 풀이
자바- 미들러 이분탐색 풀이
// case 1
// 초기 dp -> []
// 10 -> [10]
// 9 -> [9](9는 10보다 작아서)
// 2 -> [2](2는 9보다 작아서)
// 5 -> [2, 5]
// 3 -> [2, 3](5를 3으로 대체)
// 7 -> [2, 3, 7]
// 101 -> [2, 3, 7, 101]
// 18 -> [2, 3, 7, 18](101을 18으로 대체).
// case 2
// 0 -> [0]
// 1 -> [0, 1]
// 0 -> [0 ,1]
// 3 -> [0, 1, 3]
// 2 -> [0, 1, 2]
// 3 -> [0, 1, 2, 3]
class Solution {
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// dp 배열은 LIS의 현재 길이를 저장
int[] dp = new int[nums.length];
int length = 0; // 현재 LIS의 길이
for (int num : nums) {
// 이분 탐색을 사용하여 num이 dp 배열에서 적절한 위치를 찾기
int left = 0, right = length;
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
// left는 num이 들어가야 할 위치
dp[left] = num;
// length는 dp 배열의 현재 유효 길이
if (left == length) {
length++;
}
}
return length;
}
}Time: 3 ms
Space: 43.91 MB
성능부터가 엄청 개선됐다.
돌아보기
이분 탐색에 대해 공부해야겠다. 그리고 오늘 정기 모임에서 클럽장님들의 풀이 문제 수를 들었는데 적어도 500문제는 풀어야 할 것 같다. 하루에 5문제씩 100일 정도하면 코딩 테스트를 통과할 수 있지 않을까 싶다.
다음에는
완전 탐색이 나오면 이분 탐색으로 풀어보기
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
Last updated