[LeetCode] 2554. Maximum Number of Integers to Choose From a Range I

https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i/description/

leetcode - Maximum Number of Intergers to Choose From a Range I

문제 유형: 그리디

문제 난이도: Medium

 

문제

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

• The chosen integers have to be in the range [1, n].
• Each integer can be chosen at most once.
• The chosen integers should not be in the array banned.
• The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

 

정수 배열 banned와 두 개의 정수 n과 maxSum이 있다.

아래의 룰을 따라서 정수를 골라야 한다.

• 1~n사이에서 고른다.
• 각 숫자당 최대 한 번만 고른다.
• banned에 있으면 안된다.
• 합이 maxSum을 넘으면 안된다.

룰에 따라서 고른 정수들의 최대 개수를 구하시오.

 

풀이

banned조회를 빠르게 하기 위해, available 배열을 만들어서 false로 채운다. 0도 false로 한다.

나머지는 true로 해놓는다.

배열은 0~n까지 인덱스를 가지는 n+1크기로 한다.

또는 해시 테이블을 이용할 수도 있다.

 

1부터 n까지 다음을 한다:

만약 available[i]가 true이고, sum + i가 maxSum을 넘지 않는다면, sum에 i를 더하고, 개수를 1 누적한다.

 

최종 개수를 반환한다.

 

코드

C++

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        vector<bool> available(n+1, true);
        available[0] = false;
        for(int i = 0; i < banned.size(); ++i) {
            if(banned[i] > n) continue;
            available[banned[i]] = false;
        }

        int sum = 0;
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            if(available[i] && sum + i <= maxSum) {
                sum += i;
                ans++;
            }
        }

        return ans;
    }
};