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


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


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

leetcode 문제 사진

오늘도 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;
    }
}




제출 화면

leetcode 문제 맞았습니다


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

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


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

+ Recent posts