Dec 6, 2024

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

내 코드

2ms, 118.42MB

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        const int SIZE = 10'001;
        int dat[SIZE]{};

        for(int ban : banned) dat[ban] = 1;

        int curr{}, answer{};
        for(int i=1;i<=n;++i) {
            if(dat[i]) continue;
            if(curr + i > maxSum) break;
            
            curr += i;
            ++answer;
        }  
        return answer;
    }
};

Solution

Approach 1: Binary Search

71ms, 117.65MB
Complexity
- Let $m$ be the length of the banned array.
- Time Complexity: $O((m+n)\cdot \log m)$
- Space Complexity: $O(S)$ $O (S)$
  The space taken by the sorting algorithm ( $S$ $S$ ) depends on the language of implementation:
  - In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of $O(\log m)$ .

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        // Sort banned array to enable binary search
        sort(banned.begin(), banned.end());

        int count = 0;

        // Try each number from 1 to n
        for (int num = 1; num <= n; num++) {
            // Skip if number is in banned array
            if (customBinarySearch(banned, num)) continue;

            maxSum -= num;

            // Break if sum exceeds our limit
            if (maxSum < 0) break;

            count++;
        }
        return count;
    }

private:
    // Helper method to check if value exists in sorted array
    bool customBinarySearch(vector<int>& arr, int target) {
        int left = 0;
        int right = arr.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) return true;

            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
};

GPT

아래는 LeetCode 문제 “Maximum Number of Integers to Choose From a Range I”에 대한 설명과 해당 에디토리얼 솔루션 1(이진 탐색 접근법)에 대한 상세한 해설입니다.

문제 개요:
우리는 1부터 n까지의 정수 범위 안에서 몇 개의 정수를 선택하려고 합니다. 단, 선택할 수 없는 몇 개의 정수(배제 목록, banned)가 주어지고, 선택한 모든 정수의 합은 maxSum을 초과해서는 안 됩니다. 우리가 하고 싶은 것은 “선택 가능한 정수의 개수”를 최대화하는 것입니다. 즉, 가능한 많은 정수를 고르되, 배제된 정수는 포함하지 않고, 합도 maxSum 이하여야 합니다.

핵심 포인트:

선택할 수 있는 정수는 [1, n] 범위 내에서 배제되지 않은 정수들입니다.
합이 최대 maxSum을 넘어가지 않는 선에서 가능한 한 많은 정수를 고르고 싶습니다.
직관적으로, 합을 최소화하면서 많은 개수를 확보하려면, 가능한 한 “작은 수부터” 골라야 합니다. 작은 수를 먼저 고르면 적은 합으로 더 많은 개수를 담을 수 있기 때문입니다.

그러나 우리는 직접 모든 경우를 시도하기 어렵습니다(시간 복잡도 문제). 대신 이진 탐색(Binary Search)을 통해 “최대 몇 개까지 가능한지”를 추측하고 검증하는 방식을 사용할 수 있습니다.

에디토리얼 솔루션 1: 이진 탐색 (Binary Search) 설명

접근 방법은 다음과 같습니다.

배제 목록 정렬 및 전처리:
banned 배열을 정렬해 둡니다. 이렇게 하면 [1, n] 범위 내에서 특정 범위 내에 몇 개의 금지 수(banned)가 있는지, 그 인덱스 위치를 쉽게 파악할 수 있습니다.
이진 탐색으로 최대 개수 탐색:
우리가 고를 수 있는 정수의 최대 개수의 범위는 최소 0개부터 최대 (n - 배제된 수의 개수)개 까지입니다. 이 범위 내에서 이진 탐색을 수행합니다.

이진 탐색의 목표:
- mid = 어떤 가설적인 선택 개수
- “mid 개의 정수를 (배제 없이 가능한 가장 작은 정수들부터) 골랐을 때, 이들의 합이 maxSum 이하인가?”를 판별.
이 판별 과정(feasibility check)을 통해 mid를 조정하면서 최대 가능한 개수를 찾습니다.
feasibility check (검증 과정) 상세 설명:
- mid 개의 정수를 고르려 한다고 가정해 봅시다.
- 가능한 한 작은 정수부터 골라야 합니다. 가장 이상적인 상황은 [1, 2, 3, …, M] 과 같이 낮은 수부터 차례대로 고르는 것입니다. 물론 중간에 banned된 수는 건너뛰어야 합니다.
- 어떤 M에 대해, 1부터 M까지의 정수 중 banned를 제외한 허용된 정수의 개수가 mid개 이상이라면, M까지의 범위 안에서 충분히 mid개를 뽑을 수 있습니다. 이 경우, 실제로 선택하게 되는 mid개의 정수는 [1, M] 사이의 허용 가능한 가장 작은 정수들일 것입니다.
이제 합을 생각해봅시다:
- 1부터 M까지 합은 M(M+1)/2입니다.
- 여기서 banned된 수들은 실제로 고르지 않으니 sum에 포함되지 않습니다.
- 만약 1부터 M 사이에 mid개 이상의 허용 정수가 있다면, 가장 작은 mid개의 허용 정수를 선택했을 때의 합은 M(M+1)/2보다 “작거나 같게” 만들 수 있습니다. 왜냐하면 M 범위 내에 허용 정수가 mid개보다 많다면, 큰 수(예: M, M-1, …)를 빼고 더 작은 수들로 mid개를 구성할 수 있어 sum을 최소화할 수 있기 때문입니다.
따라서, M(M+1)/2 ≤ maxSum이면, 최소한 이 범위 내에서 mid개를 고를 여지는 있습니다. 만약 합이 maxSum을 넘는다면, 더 작은 개수를 시도하거나, 더 작은 범위로 줄여야 하므로 mid를 줄여야 합니다.

한 가지 주의해야 할 점은, banned가 있는 경우 실제로 mid개를 얻기 위해 M값을 더 키워야 할 수도 있다는 점입니다.
- 가령, 1부터 M까지에서 banned된 수가 많아 mid개를 확보하기 어렵다면, M을 늘려 더 큰 수 범위로 가야 합니다. 하지만 M을 늘리면 합이 증가하여 maxSum을 초과할 위험이 커집니다.
- 이 과정을 이진 탐색으로 최적의 mid를 찾습니다. 즉, 어떤 mid에 대해 충분히 작은 범위 M 내에서 mid개를 확보할 수 있고, 해당 범위의 합도 maxSum 이하라면 mid를 늘려보고, 그렇지 않다면 mid를 줄입니다.
이진 탐색 알고리즘 흐름:
- low = 0, high = n - (배제된 수의 개수)로 시작
- mid = (low + high) / 2 로 설정
- mid개를 선택 가능한지 위의 논리를 바탕으로 체크
- 가능하다면(= 합 조건 충족) low = mid + 1로 올림 (더 큰 개수가 가능한지 확인)
- 불가능하다면 high = mid - 1로 내림
- 이를 반복하다가, 가능한 최대 개수를 찾습니다.

정리:

이 문제는 “가장 많이 고를 수 있는 정수 개수”를 찾기 위해 이진 탐색을 사용하는 전략입니다.
mid (가정한 개수) 개를 고를 수 있는지 판별하기 위해서는, banned 정렬 및 prefix 계산을 통해 특정 M까지 고려했을 때 허용 가능한 정수 개수를 빠르게 구할 수 있습니다.
1부터 M까지 합이 maxSum 이하인지(또는 좀 더 정교하게, banned를 고려한 실제 선택 가능한 수들의 합이 maxSum 이하인지) 확인하여 feasibility를 판단합니다.
이 과정을 반복하며 가능한 최대 개수를 찾습니다.

이로써 문제와 해당 에디토리얼의 이진 탐색 접근법을 이해할 수 있습니다.

Approach 2: Sweep

62ms, 117.44MB
Complexity
- Let $m$ be the length of the banned array.
- Time Complexity: $O(n + m \cdot \log m)$
- Space Complexity: $O(S)$ $O (S)$
  The space taken by the sorting algorithm ( $S$ $S$ ) depends on the language of implementation:
  - In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of $O(\log m)$ .

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        sort(banned.begin(), banned.end());

        int bannedIdx = 0, count = 0;

        // Check each number from 1 to n while sum is valid
        for (int num = 1; num <= n && maxSum >= 0; num++) {
            // Skip if current number is in banned array
            if (bannedIdx < banned.size() && banned[bannedIdx] == num) {
                // Handle duplicate banned numbers
                while (bannedIdx < banned.size() && banned[bannedIdx] == num) {
                    bannedIdx++;
                }
            } else {
                // Include current number if possible
                maxSum -= num;
                if (maxSum >= 0) {
                    count++;
                }
            }
        }
        return count;
    }
};

GPT

아래는 LeetCode 문제 “Maximum Number of Integers to Choose From a Range I”에 대한 두 번째 접근법(Approach 2: Sweep) 설명입니다.

문제 개요 복습:
1부터 n까지의 수 중에서 몇 개의 정수(banned)는 고를 수 없습니다. 나머지 허용된 정수들 중에서 가능한 한 많이 선택하되, 그 선택한 정수들의 합이 maxSum을 초과하지 않도록 해야 합니다. 목표는 “고를 수 있는 정수의 최대 개수”를 구하는 것입니다.

Approach 2: Sweep(선형 스캔) 방법의 아이디어:

우리는 가능한 한 작은 수부터 골라서 합을 최소로 유지하면서 최대 개수를 확보하려고 합니다. 단순히 1부터 n까지 순서대로 살펴보며, banned인 경우 스킵하고, 아닌 경우 합에 더해나가다가 maxSum을 넘기기 직전까지 선택을 계속하면 됩니다. 그러나 n이 매우 클 수 있으므로, 단순히 1씩 증가시키며 확인하는 것은 비효율적입니다.

이러한 비효율을 피하기 위해 “구간별”로 한 번에 처리하는 방식을 취합니다. 이를 “스위프(sweep)“한다고 표현하는데, 이는 1부터 n까지의 숫자라인을 훑어가며, banned로 인해 나뉜 구간(interval)마다 한 번에 몇 개를 담을 수 있는지 계산하는 방식입니다.

구체적인 방법:

banned 배열 정렬:
banned 리스트를 정렬하면, 허용되지 않은 숫자들이 오름차순으로 정렬됩니다. 이로써 [1, n] 범위에서 banned 숫자들 사이에 생기는 “허용 정수 구간”들을 명확히 파악할 수 있습니다.

예를 들어, n=10이고 banned = [2, 5, 7]이라고 하면, 허용 가능한 정수 구간은 다음과 같이 나뉩니다.
- [1], [3,4], [6], [8,9,10]
구간별로 처리하기:
이제 1부터 시작해서, banned 숫자들이 있는 지점을 기준으로 연속된 허용 정수 구간을 고려합니다. 각 구간을 처리할 때, 그 구간에 속한 숫자들을 가장 작은 수부터 하나씩 추가해나가면 됩니다. 하지만 이때도 하나씩 추가하는 대신, 등차수열의 합 공식을 사용해 그 구간 내에서 한 번에 얼마나 많은 수를 골라낼 수 있는지 계산할 수 있습니다.
- 예를 들어, 구간 [3,4]를 고려한다고 합시다. 이 구간 내의 숫자 합은 3+4=7이며, 개수는 2개입니다.
- 더 큰 구간 예: [8,9,10]의 합은 8+9+10 = 27이며, 개수는 3개입니다.
이때, 우리가 maxSum 한도 내에서 얼마나 많은 수를 추가할 수 있는지는 다음과 같이 결정할 수 있습니다.
- 현재까지 이미 뽑은 수의 합 = currentSum (초기 0)
- 새로운 구간 [L, R] (L~R 전체 허용)
- [L, R]의 수들을 하나씩 추가하면, 합은 (L + (L+1) + … + R) = (R-L+1)*(L+R)/2 (등차수열 합 공식)
  하지만 여기서는 L부터 R까지 전부 다 담을 수 없을 수도 있으므로, 우선 R-L+1(구간의 길이) 전체를 더했을 때 maxSum을 초과하는지 체크합니다. 만약 초과한다면, 전체를 담을 수 없으니 더 적은 수만큼 담을 수 있는지 계산해야 합니다.
이 계산 과정은 다음과 같이 이뤄집니다:
- 구간 안에서 몇 개의 정수를 추가했을 때의 합을 등차수열 합 공식으로 쉽게 구할 수 있으므로, 적절한 개수를 이분 탐색하거나 직접 수식 변형 등을 통해 빠르게 찾아낼 수 있습니다. (에디토리얼에서는 이 과정을 단순화해서 설명하고 있습니다.)
- 즉, 구간 내에서 가능한 많은 수를 담되, currentSum + 부분합 ≤ maxSum이 되어야 합니다.
연속 구간 활용의 장점:
만약 banned가 많지 않고, 허용 구간이 몇 안 된다면, 각 구간을 처리하는 것은 매우 빠릅니다.
구간을 [start, end]라 할 때, 이 구간 내의 정수 합은 등차수열 합공식으로 O(1)에 계산 가능하므로, 각 구간마다 “한 번에” 담을 수 있는 최대 개수를 확정할 수 있습니다.
전체 알고리즘 흐름:
- banned 정렬
- 이전 banned 수 바로 다음 수부터 다음 banned 수 바로 전 수까지를 허용 구간으로 잡음
- 각 허용 구간마다:
  - 가능한 최대 개수를 sum 제한(maxSum) 안에서 담을 수 있는 만큼 담는다.
  - 담을 수 있는 개수를 최대화하고, sum을 업데이트
  - sum이 maxSum을 넘지 않는 선에서 계속 진행
- 마지막 구간(가령, 마지막 banned 이후 n까지, 또는 banned가 없는 경우 1부터 n까지)까지 처리한 뒤, 더 이상 추가 불가능하면 종료
- 누적된 개수가 곧 선택한 정수의 최대 개수

정리:
이 Approach 2 (Sweep) 방식은 [1, n] 범위를 banned를 기준으로 나눈 뒤, 각 허용 구간에서 최소부터 최대까지의 합을 한 번에 빠르게 계산하여, sum 제약(maxSum)을 초과하지 않는 최대 개수를 효율적으로 결정하는 방법입니다.
이렇게 하면 일일이 한 숫자씩 확인할 필요 없이, 등차수열 합 공식으로 한 번에 계산하므로 시간 복잡도를 줄이고 효율적인 계산이 가능합니다.

요약하자면, “Sweep” 기법은 n까지 선형적으로 나아가며(훑으며), allowed 구간을 만나면 그 구간에서 뽑을 수 있는 최대 정수 개수를 한 번에 계산하고, sum 제약을 만족하는 선에서 최대 개수를 갱신하는 접근법입니다.

Approach 3: Hash Set

175ms, 177.92MB
Complexity
- Let $m$ be the length of the banned array.
- Time Complexity: $O(m + n)$
- Space Complexity: $O(m)$

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        // Store banned numbers in an unordered_set
        unordered_set<int> bannedSet(banned.begin(), banned.end());

        int count = 0;

        // Try each number from 1 to n
        for (int num = 1; num <= n; num++) {
            // Skip banned numbers
            if (bannedSet.count(num)) continue;

            // Return if adding current number exceeds maxSum
            if (maxSum - num < 0) return count;

            // Include current number
            maxSum -= num;
            count++;
        }
        return count;
    }
};

GPT

아래는 동일한 문제( “Maximum Number of Integers to Choose From a Range I” )에 대한 Approach 3 (Hash Set 이용) 방식의 설명입니다.

문제 다시 복습:
1부터 n까지의 정수 중에서 금지된 정수(banned)가 있습니다. banned에 속하지 않는 정수들을 가능한 한 많이 선택하되, 그 선택한 정수들의 합이 maxSum 이하가 되게 하고 싶습니다. 목표는 선택할 수 있는 최대 정수의 개수를 구하는 것입니다.

Approach 3: Hash Set(해시 셋) 이용한 단순 시뮬레이션

이 접근법은 가장 직관적인 방식으로, 1부터 시작해 n까지 순서대로 확인하면서:

해당 숫자가 banned에 속하는지 확인
banned가 아니라면, 지금까지 선택한 정수들의 합에 이 숫자를 더해도 maxSum을 초과하지 않는지 확인
초과하지 않는다면 그 수를 선택(개수 +1, 합 갱신), 초과한다면 더 이상 큰 수는 당연히 더 많이 합을 키우므로 선택 불가능 → 여기서 중단

이렇게 하면 결국 가장 작은 수부터 가능한 한 많이 선택하게 됩니다. 왜냐하면 1부터 시작해서 순서대로 올라가며 고르기 때문입니다. 이렇게 작은 수부터 채워나가면 합을 최소로 유지하면서 최대 개수를 얻을 수 있습니다.

구체적인 절차:

banned 목록을 해시 셋(집합)으로 만들어 둡니다. 이렇게 하면 각 숫자가 banned인지 O(1)에 판단할 수 있습니다.
sum = 0, count = 0으로 초기화합니다.
i를 1부터 n까지 순회:
- 만약 i가 banned에 속한다면 넘어갑니다.
- 만약 i가 banned가 아니고, sum + i ≤ maxSum 이라면:
  - sum += i
  - count += 1
- 만약 sum + i > maxSum 이라면, i 이후의 수(i+1, i+2, …)는 i보다 더 크므로 합을 더욱 키워 maxSum을 초과하게 됩니다. 따라서 더 이상 진행할 필요 없이 중단합니다.
count를 반환합니다. 이것이 최대 선택 개수입니다.

복잡도와 특징:

이 방식은 O(n) 시간에 가능하며, 해시 셋 덕분에 banned 검사도 O(1)에 할 수 있습니다.
매우 직관적이고 구현하기 쉽지만, n이 아주 클 경우 시간 초과 우려가 있을 수 있습니다. 그런 상황에서는 더 효율적인 이진 탐색이나 스위프 기법(Approach 1, 2)을 고려할 수 있습니다.

정리하면, Approach 3(Hash Set)은 단순히 1부터 n까지 차례로 순회하면서 banned를 건너뛰고, 가능한 한 많이 선택하다가 더 이상 maxSum을 넘지 않게 선택할 수 없을 때 멈추는 단순/직관적 시뮬레이션 방법입니다.