- Problem

2389. Longest Subsequence With Limited Sum

---

- 내 풀이 (greedy)

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        prefix_sum = list(accumulate(sorted(nums)))
        answer = []

        for query in queries:
            result = 0
            for i, v in enumerate(prefix_sum):
                if v <= query:
                    result = i+1
                else:
                    break
            answer.append(result)
        
        return answer

• Complexity
  - Time Complexity O(m*n + n)
  - Space Complexity O(n)

- 결과

---

- 이분 탐색 풀이

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        prefix = list(accumulate(sorted(nums)))
        return [bisect.bisect_right(prefix, i) for i in queries]

• Complexity
  - Time Complexity O(mlogn + n)
  - Space Complexity O(n)

- 결과

Merry Christmas

          *
        * * *
      * * * * *
    * * * * * * * 
  * * * * * * * * * 
* * * * * * * * * * *
        |   |
     \---------/
      \_______/