[LeetCode/Easy] 2389. Longest Subsequence With Limited Sum

1. Input

1) int[] nums

2) int[] queries

 

2. Output

1) 다음을 따라 만든 배열을 반환

- i번째 요소에 nums의 요소들의 합이 queries[i] 이하인 nums의 부분 배열 중 길이가 가장 긴 것을 찾아 그 길이를 저장

- 부분 배열은 nums상에서 연속적일 필요는 없다.

 

3. Constraint

1) n == nums.length

2) m == queries.length

3) 1 <= n, m <= 1000

4) 1 <= nums[i], queries[i] <= 10^6

 

4. Example

Input: nums = [4,5,2,1], queries = [3,10,21] -> Output: [2,3,4]

설명:

- 0번째: 합이 3 이하인 부분 배열 중 길이가 가장 긴 것은 [2,1]이다. -> 2

- 1번째: 합이 10 이하인 부분 배열 중 길이가 가장 긴 것은 [4,5,1]이다. -> 3

- 2번째: 합이 21 이하인 부분 배열 중 길이가 가장 긴 것은 [4,5,2,1]이다. -> 4

 

5. Code

1) 첫 코드(2023/06/26)

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int[] ans = new int[queries.length];
        Arrays.sort(nums);
        for(int i=0 ; i<queries.length ; i++){
            int sum = 0, j = 0, count = 0;
            while(j<nums.length){
                sum += nums[j++];
                if(sum<=queries[i]) count++;
                else break;
            }
            ans[i] = count;
        }
        return ans;
    }
}

- 49%, 62%