[99클럽 코테 스터디 29일차 TIL] Longest Increasing Subsequence - Java [자바][LeetCode]

 

 

📜 문제 내용

 

🤔 과정

• 주어진 nums 배열의 숫자를 순회하면서 하한선을 찾고 dp 배열을 업데이트 시킨다. 
• 하한선을 찾을 때 이분 탐색을 이용하며 시간복잡도는 O(logN)이다. 그리고 최초의 반복문에 따라 총 시간 복잡도는 O(N logN) 이 된다. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

class Solution {
    private int[] dp;
    
    public int lengthOfLIS(int[] nums) {
        dp = new int[nums.length];
        dp[0] = nums[0];

        int maxLen = 1;

        for(int i = 1; i < nums.length; i++){
            if(nums[i] > dp[maxLen - 1]){
                dp[maxLen++] = nums[i];
            } else {
                int pos = findLowerBound(nums[i], 0, maxLen - 1);
                dp[pos] = nums[i];
            }
        }

        return maxLen;
    }

    private int findLowerBound(int num, int start, int end){
        while(start < end){
            int mid = (start + end) / 2;

            if(dp[mid] < num) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

 

• 이분 탐색 구현은 무난했다. 

 

✍️ 재제출 답안 - 🙆‍♂️ 통과

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> dp = new ArrayList<>();
        
        for (int num : nums) {
            int pos = Collections.binarySearch(dp, num);
            
            if (pos < 0) pos = -(pos + 1); 

            if (pos < dp.size()) {
                dp.set(pos, num); 
            } else {
                dp.add(num); 
            }
        }
        
        return dp.size(); 
    }
}

 

• Collections 클래스 안에 binarySearch 메서드가 있는 것을 알고 있어서 한 번 적용해보고자 시도해봤다. 
• 하지만 최초에 구현한 이분 탐색보다는 조금 차이가 있는 결과가 나왔다. 

 

🔗 문제 링크

• LeetCode - Longest Increasing Subsequence (링크)