2389. Longest Subsequence With Limited Sum

문제 링크 : https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/

nums와 queries가 주어졌을 때,
각 queries보다 크지 않은 nums의 개수들의 배열을 반환하라

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        ans = []
        for q in queries:
            cnt = 0
            for n in nums:
                if q >= n:
                    q -= n 
                    cnt +=1
                else:
                    break
            ans.append(cnt)
        return ans

nums를 정렬하고 쿼리보다 크기 전까지 쿼리에서 nums 배열들을 빼주고 개수를 count해준다.

time complexity : sort -> O(nlogn),
이중 for 문을 돌면서 mn(numsqueries)

총 O(m⋅n+n⋅log⁡n)의 시간복잡도가 걸린다.

space complexity : 정렬할때 O(n)의 추가적인 space가 든다