LeetCode : 2389. Longest Subsequence With Limited Sum

 

문제)

 

길이가 n인 배열 정수 nums와 길이가 m인 정수배열 queries가 주어진다.

 

길이 m의 배열 answer를 반환.

여기서 answer[i]는 요소의 합계가 queries [i]보다 작거나 같도록 nums에서 가져올 수 있는 시퀀스의 최대 크기입니다.

 

부분 수열은 다른 배열에서 일부 또는 전부의 요소를 순서를 변경하지 않고 삭제하여 만들 수 있는 배열.

 

문제 난이도 : 하

 

소요시간 및 풀이)

우리는 sub sequence의 최대 크기만 구하면 되지 진짜 안에 있는 요소까지 구할 필요는 없다.

그래서 배열을 오름차순으로 정렬해서 하나씩 비교해나가는 방식으로 풀었다.

 

nums를 오름차순으로 정렬해주었다.

그 후 ranged-for문으로 query를 가져와서 num과 비교.

sum과 num의 합이 query 보다 작으면 sum+=num과 count++를 해주고 넘어감.

만약 sum과 num의 합이 query보다 크면 break; 하고 count를 answer에 넣어준다.

 

소요 시간 : 14분

 

정답 코드

class Solution 
{
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) 
    {
        vector<int> answer;

        sort(nums.begin(), nums.end());

        for (int query : queries)
        {
            int sum = 0;
            int count = 0;

            for (int num : nums)
            {
                if (sum + num <= query)
                {
                    sum += num;
                    count++;
                }
                else
                {
                    break;
                }
            }

            answer.push_back(count);
        }

        return answer;
    }
};