Leetcode 2389. Longest Subsequence with Limited Sum (Binary Search, Prefix Sum)

https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/

Longest Subsequence With Limited Sum - LeetCode

---

메리크리스마스~ 오랜만에 작성하는 에러 코드이네요

요새 자바를 배워서 자바와 파이썬을 같이 생각하려는 연습을 하고 있는데요.

 

Leetcode 난이도 easy이지만 생각할거리가 있는 문제를 가지고 왔습니다. (문제 제대로 안 읽고 헤맸었던 문제 ㅜㅠ)

nums라는 리스트의 조합의 합 중에서, queries의 각 요소보다 같거나 작은 조합 중 그 길이가 가장 긴 값을 제시하라는 문제인데요. 파이썬과 자바 코드 각각을 살펴보겠습니다.

 

이 문제에서 가장 먼저 해야 할일은 바로 sorting 입니다.

대소관계를 비교하면서 갯수를 찾아야 할 때 => 정렬을 하면 훨씬 빠르고 쉽게 값을 찾을 수 있기 때문이죠

 

Source: Leetcode

이렇게 정렬을 하고 나서 누적된 값의 합을 비교해야 할 때 => Prefix Sum

미리 기존 정렬의 누적 합을 새로운 리스트화한 Prefix Sum을 만들면 효과적으로 문제를 풀 수 있는데요

 

여기서 주의해야 할 점은!! 새로운 array를 만든다 => 공간을 더 써야한다이기 때문에

문제의 환경에 따라서 기존 nums 리스트에 값을 교체하는 형식의 in-place접근을 고려해야 합니다.

(이 문제 역시 기존의 nums를 prefix sum으로 바꾸는 과정을 거쳤습니다)

 

파이썬 코드)

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        for i in range(1,len(nums)):
            nums[i] += nums[i-1]

        ans = []

        for q in queries:
            idx = bisect.bisect(nums,q)
            ans.append(idx)
        
        return ans

앞서 제시한 바와 같이 nums를 정렬하고 -> 1부터 nums를 돌면서 nums[i] += nums[i-1] 현재값에 이전 값을 더해가면서 prefix sum을 만듭니다. 그리고 이제 queries에서 도출한 값이 어느위치에 있는지를 bisect를 이용해서 효율적으로 탐색합니다.

 

(Bisect 가 뭔지 모르겠다면 아래 글을 참고 바랍니다)

2022.09.30 - [Python] - Python bisect 배열 이진 분할 알고리즘 정리

 

 

Java 코드)

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        for(int i=1; i < nums.length; ++i)
            nums[i] += nums[i-1];

        int n = queries.length;
        int ans[] = new int[n];
        for(int i=0; i < n; ++i){
            int idx = binarySearch(nums,queries[i]);
            ans[i] = idx;
        }
        return ans;
    }
    int binarySearch(int[] nums, int target){
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = (l+r)/2;
            if(nums[mid]==target)
            return mid +1;
            if (nums[mid]<target)
            l = mid+1;
            else
            r = mid -1;
        }
        return nums[l] > target? l : l+1;
    }
}

Java는 sort 를 위해 Arrays.sort()를 사용합니다.

그리고  하단에 binarySearch 함수를 만들어서 binary search 를 사용합니다.

if else구문에서 함수영역이 1줄이여서 {}를 생략하여 식이 훨씬 더 깔끔해진 것 같습니다.