Today's Challenge

fabichoi 2022. 12. 25. 23:45

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

Longest Subsequence With Limited Sum - LeetCode

Longest Subsequence With Limited Sum - You are given an integer array nums of length n, and an integer array queries of length m. Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that

leetcode.com

누적합으로 연산하는거 까지는 생각을 했는데
sort를 사전에 해서 index로 이분 탐색하는 건 생각을 못함 ㅠ_ㅠ

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        pre_sum = [0]

        for n in nums:
            pre_sum.append(pre_sum[-1] + n)
        
        res = []

        for q in queries:
            idx = bisect_right(pre_sum, q)
            res.append(idx-1)
        
        return res