[LeetCode] 2389번 Longest Subsequence With Limited Sum 문제를 풀어보았다. (ft. java)

2022년 12월 25일 일요일 - 메리 크리스마스~~

오늘 올려볼 문제는 2389번 Longest Subsequence With Limited Sum 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

이진 탐색 변형을 익힌다고 생각보다 오래걸렸음..

입력

사진에서도 볼 수 있듯이 int 배열 2개가 입력으로 들어온다.

---

풀이 및 코드

nums의 subsequence 중에 합이 queries[i] 보다 같거나 작은 subsequence 중 가장 긴 길이를 구해서 배열로 리턴하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

nums를 정렬하고 그 index까지의 합을 구해서 저장한다. ex) nums = {1,2,3,4} -> {1,3,6,10}

이후 이진 탐색을 통해서 queries[i]보다 같거나 작은 값을 nums에서 이진 탐색으로 찾는다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        var result = new int[queries.length];
        
        Arrays.sort(nums);
        
        for(int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        
        for(int i = 0; i < result.length; i++) {            
            result[i] = find(nums, queries[i]);
        }
        
        return result;
    }
    
    public int find(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

---

제출 화면

이진 탐색 변형에 좀 약한걸 알고있었어서 익힐겸 고민을 좀 했더니 이지문제에 생각보다 많은 시간을 썼다.

하지만 충분히 익힌 것 같으니 도움이 된 것 같다!

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.