문제 링크

내 코드

427ms, 301.06MB

class Solution {
public:
    int maximumLength(string s) {
        // 다 만들기
        int len = static_cast<int>(s.length()); // ~ 50
        unordered_map<string, int> m;
        int answer{-1};
        for(int i{};i<len;++i) {
            for(int j{i};j<len;++j) {
                string now = s.substr(i, j - i + 1); // (index, length)
                // single check..
                char last = now[0];
                bool chk{};
                for(int k{1}, e{static_cast<int>(now.length())}; k < e;++k) {
                    if(last != now[k]) {
                        chk = true;
                        break;
                    }
                }
                if(chk) continue; // not special

                if(m.count(now)) {
                    m[now]++;
                    if(m[now] >= 3) {
                        answer = max(answer, static_cast<int>(now.length()));
                    }
                }
                else {
                    m.emplace(now, 1);
                }
            }
        }

        return answer;
    }
};

GPT가 준 아이디어

해당 문제 상황을 정리해보면 다음과 같습니다:

• 1부터 최대 10만 정도의 범위의 정수 배열이 존재한다고 가정합니다.
• 주어진 [start, end] 구간에 대해 일괄적으로 +1 증가 연산을 여러 번 수행합니다.
• 모든 증가 연산이 끝난 뒤, 최종적으로 해당 배열에서 가장 카운트가 높은(값이 가장 큰) 원소를 찾아야 합니다.

이러한 요구사항에 대해 어떤 자료구조나 기법을 사용할 수 있을까요?

1. 단순 누적(difference array) 기법

만약 “모든 구간 업데이트 후 한 번에 결과를 확인”하는 상황이라면, 가장 간단하고 빠른 방법 중 하나는 차분 배열(difference array)을 사용하는 것입니다.

방법:

1. 길이 N (여기서는 N=10만)인 배열 arr를 0으로 초기화합니다.
2. 별도로 길이 N+1 (또는 N)인 차분 배열 diff를 0으로 초기화합니다.
3. 각 업데이트 쿼리 [l, r]에 대하여:
   • diff[l] += 1
   • diff[r+1] -= 1 (r이 배열 범위 내일 경우)
4. 모든 업데이트를 마친 뒤, diff 배열에 대해 prefix sum을 한 번 수행하면 arr 배열의 최종 상태가 됩니다.
   • 예: arr[1] = diff[1], arr[i] = arr[i-1] + diff[i] (1-based 인덱스 가정 시)
5. arr 배열을 전부 순회하며 최댓값을 O(N) 안에 찾을 수 있습니다.

복잡도:

• M개의 업데이트 쿼리가 있을 경우, diff 배열 업데이트는 각 쿼리당 O(1)이므로 총 O(M)입니다.
• 최종 prefix sum과 최대값 탐색에 O(N) 소요됩니다.

N=100,000, M도 유사한 수준이라면 충분히 빠른 시간 안에 처리 가능합니다. 이 방법의 장점은 “중간에 최대값을 자주 묻지 않고, 마지막에 한 번만 필요” 하다면 아주 효율적이라는 점입니다.

단점은 “업데이트 도중에 현재 최대값을 실시간으로 알고 싶다”거나 “중간에 상태를 자주 질의”하는 경우에는 이 방법만으로는 곤란하다는 것입니다.

2. 세그먼트 트리(Segment Tree) 또는 펜윅 트리(Fenwick Tree)

• Segment Tree with Lazy Propagation:
  구간에 대한 업데이트(증가)와 구간에 대한 최대값 질의를 모두 O(log N)에 처리할 수 있는 자료구조입니다.

  • Range update(+1 on [l,r])와 Range max query를 동시에 지원하기 위해서는 세그먼트 트리에 lazy propagation(지연 전파)을 적용해야 합니다.
  • 이 경우, 업데이트 횟수가 많고 중간중간 최댓값을 질의해야 한다면 세그먼트 트리가 유용합니다.

• Fenwick Tree (BIT):
  Fenwick 트리는 주로 구간 합 연산 및 점 쿼리에 특화되어 있어, 구간 최대값 질의나 구간 업데이트와 최대값 질의의 조합에는 적합하지 않습니다. Fenwick 트리는 합을 다루기엔 좋지만 최대값을 다루기엔 비효율적입니다.

정리

• 모든 구간 업데이트를 마친 뒤 한 번만 최대값을 알고 싶다면: 차분 배열(difference array) 를 활용한 O(N) 후처리가 가장 간단하고 빠릅니다.
• 업데이트와 최대값 쿼리가 실시간으로 섞여있고 빠른 쿼리 응답이 필요하다면: 지연 전파(Lazy Propagation) 세그먼트 트리를 구축하는 것이 일반적입니다.

따라서 상황에 따라 자료구조 선택:

• 최종 한 번 최대값 확인: 차분 배열 후 prefix sum (간단, 효율적)
• 중간 쿼리 다수 존재, 실시간 업데이트 및 최대값 확인: 세그먼트 트리(lazy propagation) 사용

그 중 difference array 사용하기.

---

아래는 예시를 들어 차분 배열(difference array)와 prefix sum을 이용해 구간 카운트 업데이트를 진행한 뒤 최대값을 구하는 과정을 설명하고, 그에 해당하는 C++ 예제 코드를 제시하겠습니다.

개념 설명 예시

예를 들어, N=10인 배열이 있다고 합시다. 처음에는 arr = [0,0,0,0,0,0,0,0,0,0] 으로 모두 0입니다. (편의상 1-based indexing 사용)

M=3개의 업데이트 쿼리가 있다고 가정합시다:

1. [2, 5] 구간에 모두 +1
2. [3, 7] 구간에 모두 +1
3. [1, 3] 구간에 모두 +1

각 쿼리를 차분 배열(diff)로 처리하는 과정을 보여드리겠습니다.

차분 배열(difference array) 기법

• diff 배열을 arr와 동일한 크기(또는 N+1 크기)로 준비하고 모두 0으로 초기화합니다.
  초기 상태: diff = [0,0,0,0,0,0,0,0,0,0,0] (여기서는 편의상 인덱스를 1부터 10까지, 11번째는 패딩)

1번 쿼리 [2,5]

• diff[2] += 1
• diff[5+1] -= 1 → diff[6] -= 1 적용 후 diff = [0,0,1,0,0,0,-1,0,0,0,0]

2번 쿼리 [3,7]

• diff[3] += 1
• diff[7+1] -= 1 → diff[8] -= 1 적용 후 diff = [0,0,1,1,0,0,-1,0,-1,0,0]

3번 쿼리 [1,3]

• diff[1] += 1
• diff[3+1] -= 1 → diff[4] -= 1 적용 후 diff = [0,1,1,1,-1,0,-1,0,-1,0,0]

이제 모든 쿼리 처리를 마친 diff 배열은 다음과 같습니다.

diff = [0, 1, 1, 1, -1, 0, -1, 0, -1, 0, 0]

prefix sum으로 실제 arr 복원

diff 배열을 누적합(prefix sum)하면 실제 arr 값을 얻을 수 있습니다.

• arr[1] = diff[1] = 1
• arr[2] = arr[1] + diff[2] = 1 + 1 = 2
• arr[3] = arr[2] + diff[3] = 2 + 1 = 3
• arr[4] = arr[3] + diff[4] = 3 + (-1) = 2
• arr[5] = arr[4] + diff[5] = 2 + 0 = 2
• arr[6] = arr[5] + diff[6] = 2 + (-1) = 1
• arr[7] = arr[6] + diff[7] = 1 + 0 = 1
• arr[8] = arr[7] + diff[8] = 1 + (-1) = 0
• arr[9] = arr[8] + diff[9] = 0 + 0 = 0
• arr[10] = arr[9] + diff[10] = 0 + 0 = 0

결과적으로 arr = [1,2,3,2,2,1,1,0,0,0] 이 됩니다.

이 중 최댓값은 arr[3] = 3입니다.

이런 식으로 모든 구간 업데이트를 O(M)으로 마치고, prefix sum으로 O(N)에 최종 값을 복원한 뒤 최대값을 O(N) 안에 찾을 수 있습니다.

C++ 코드 예제

아래는 위 개념을 코드로 구현한 예제입니다.
입력 형식 예:

• 첫 줄: N M
• 다음 M개의 줄: start end 형태의 구간 정보

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    // diff 배열 준비. 1-based 인덱스를 가정하므로 N+1까지 확보
    vector<long long> diff(N+2, 0);

    for (int i = 0; i < M; i++) {
        int start, end;
        cin >> start >> end;
        diff[start] += 1;
        if (end + 1 <= N) {
            diff[end+1] -= 1;
        }
    }

    // prefix sum을 통해 실제 arr 값 복원
    // arr[i] = arr[i-1] + diff[i]
    // 여기서는 arr를 별도 선언하지 않고 diff를 재활용합니다.
    long long max_val = LLONG_MIN;
    for (int i = 1; i <= N; i++) {
        diff[i] += diff[i-1]; // prefix sum
        if (diff[i] > max_val) {
            max_val = diff[i];
        }
    }

    cout << max_val << "\n";

    return 0;
}

코드 동작 방식

1. diff 배열을 0으로 초기화한 뒤, M개의 쿼리([start, end])를 읽습니다.

   • diff[start]에 +1, diff[end+1]에 -1을 합니다(end+1이 범위 내일 경우).

2. 모든 쿼리가 끝난 뒤, diff 배열에 대해 1부터 N까지 prefix sum을 계산합니다.

   • 이 과정에서 diff[i]는 최종 arr[i] 값을 의미하게 됩니다.

3. prefix sum 과정 중 바로 최대값을 갱신하여 최댓값을 출력합니다.

이러한 방법은 구간 업데이트를 매우 빠르고 간단히 처리할 수 있으며, 마지막에 한 번만 최대값을 필요로 할 때 특히 효율적입니다.

Solution

Approach 1: Binary Search

• 87ms, 105.00MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(\log n)$

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int maxBeauty = 0;

        for (int i = 0; i < nums.size(); i++) {
            // Find the farthest index where the value is within the range
            // [nums[i], nums[i] + 2*k]
            int upperBound = findUpperBound(nums, nums[i] + 2 * k);
            // Update the maximum beauty based on the current range
            maxBeauty = max(maxBeauty, upperBound - i + 1);
        }
        return maxBeauty;
    }

private:
    // Helper function to find the largest index where arr[index] <= val
    int findUpperBound(vector<int>& arr, int val) {
        int low = 0, high = arr.size() - 1, result = 0;

        // Perform binary search to find the upper bound
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= val) {
                result = mid;  // Update the result and move to the right half
                low = mid + 1;
            } else {
                high = mid - 1;  // Move to the left half
            }
        }
        return result;
    }
};

GPT

아래 코드는 주어진 배열 nums를 정렬한 뒤, 각 원소를 시작점으로 하여 [값, 값+2*k] 범위 내에 들어갈 수 있는 원소들이 몇 개나 연속해서 있는지를 이분 탐색으로 찾아 그 중 최댓값을 구하는 방식으로 동작합니다. 이 로직은 “배열 내에서 특정 구간에 들어가는 원소들의 최대 개수를 찾는 문제”를 해결하는 전형적인 방법입니다.

코드 동작 설명:

1. 정렬:

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

   배열을 오름차순으로 정렬합니다. 이렇게 하면 투 포인터나 이분 탐색을 이용해 범위 내 원소들을 쉽게 찾을 수 있습니다.

2. 메인 로직:

   int maxBeauty = 0;
   
   for (int i = 0; i < nums.size(); i++) {
       // 현재 nums[i]를 시작점으로 할 때 [nums[i], nums[i] + 2*k] 범위 내 
       // 들어가는 원소들의 최대 개수를 구한다.
       int upperBound = findUpperBound(nums, nums[i] + 2 * k);
       maxBeauty = max(maxBeauty, upperBound - i + 1);
   }
   return maxBeauty;

   • nums[i]를 시작점으로 정하고, 이 값에 2*k를 더한 범위 nums[i] + 2*k를 상한으로 합니다.

   • findUpperBound 함수를 이용해 nums[i] + 2*k 이하인 원소들 중 가장 오른쪽 인덱스를 찾습니다.

   • upperBound - i + 1는 i 인덱스부터 upperBound 인덱스까지가 모두 [nums[i], nums[i] + 2*k] 범위에 들어간다는 뜻이므로, 이 구간의 길이를 나타냅니다.

   • 모든 i에 대해 이를 계산하면서 가장 긴 구간(가장 많은 원소를 포함하는 구간)을 찾으면 그것이 최대 beauty가 됩니다.

3. findUpperBound 함수:

   int findUpperBound(vector<int>& arr, int val) {
       int low = 0, high = arr.size() - 1, result = 0;
   
       while (low <= high) {
           int mid = low + (high - low) / 2;
           if (arr[mid] <= val) {
               result = mid;  
               // 현재 mid 위치의 값이 val 이하이므로 result를 갱신하고 범위를 오른쪽으로 이동
               low = mid + 1;
           } else {
               // arr[mid] > val이면 범위를 왼쪽으로 이동
               high = mid - 1;
           }
       }
       return result;
   }

   이진 탐색을 통해 arr에서 val 이하인 원소의 최대 인덱스를 찾습니다.

   • arr[mid] <= val이면 mid 인덱스까지는 조건 충족이므로 result를 mid로 갱신하고 좀 더 오른쪽에 조건을 충족하는 원소가 없는지 확인하기 위해 low = mid + 1로 이동합니다.
   • arr[mid] > val이면 더 작은 인덱스 쪽에서 답을 찾아야 하므로 high = mid - 1로 이동합니다.

   반복문 종료 후 result는 val 이하인 가장 오른쪽 인덱스를 가리키게 됩니다.

정리:

• 배열 정렬 후, 각 원소를 시작점으로 하는 유효 범위([값, 값+2*k])를 설정하고 이 범위 내 최대 원소 개수를 찾습니다.
• 이를 위해 이분 탐색으로 상한 범위(nums[i] + 2*k) 이하인 원소들 중 가장 오른쪽 인덱스를 찾는 방식으로 O(n log n) 시간에 처리할 수 있습니다.
• 최종적으로 모든 시작점에 대해 최대 길이를 비교하고 그 최댓값을 반환합니다.

Approach 2: Sliding Window

• 47ms, 104.86MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(\log n)$

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int right = 0;  // Pointer for the end of the valid range
        int maxBeauty = 0;

        // Iterate through the array with the left pointer
        for (int left = 0; left < nums.size(); left++) {
            // Expand the right pointer while the range condition is met
            while (right < nums.size() && nums[right] - nums[left] <= 2 * k) {
                right++;
            }
            // Update the maximum beauty based on the current range
            // We do not add 1 here as right is already pointing to one position
            // beyond the valid range.
            maxBeauty = max(maxBeauty, right - left);
        }
        return maxBeauty;
    }
};

GPT

이 코드는 이전 코드와 비슷한 목표를 가지지만, 투 포인터(two-pointer)나 슬라이딩 윈도우 기법을 사용해서 더 효율적이고 직관적으로 문제를 해결합니다.

아이디어:
정렬된 상태에서, left와 right 두 개의 포인터를 이용해 [left, right) 구간이 주어진 조건(nums[right] - nums[left] <= 2 * k)을 만족하는 최대 길이를 찾습니다. 이 구간 내의 모든 원소는 nums[left]와의 차이가 2k 이내이므로, 어떤 기준점을 잡더라도 [값, 값+2k] 범위 안에 구간의 모든 원소를 포함할 수 있습니다.

자세한 동작 설명:

1. 정렬:

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

   배열을 오름차순 정렬합니다. 이렇게 하면 작은 값에서 큰 값으로 순서가 정해져, 연속 구간을 슬라이딩 윈도우로 다루기 쉬워집니다.

2. 투 포인터 초기화:

   int right = 0;   // 오른쪽 포인터
   int maxBeauty = 0;

   오른쪽 포인터 right를 0으로, 최대 길이를 0으로 초기화합니다.

3. 슬라이딩 윈도우 확장:

   for (int left = 0; left < nums.size(); left++) {
       // nums[right] - nums[left] <= 2*k를 만족하는 동안 right를 확장
       while (right < nums.size() && nums[right] - nums[left] <= 2 * k) {
           right++;
       }
       // 여기서 right는 조건을 만족하지 않는 첫 번째 인덱스 또는 배열의 끝
       
       maxBeauty = max(maxBeauty, right - left);
   }

   • left 포인터를 0부터 시작하여 끝까지 증가시키면서, right 포인터를 이동시킵니다.
   • nums[right] - nums[left] <= 2*k 조건이 유지되는 한 right를 계속 오른쪽으로 확장하여 가능한 최대 구간을 찾습니다.
   • 조건을 만족하지 않으면 while 루프를 빠져나오게 되고, 이 시점에서 [left, right) 구간은 조건을 만족하는 최대 길이의 구간입니다.
   • maxBeauty는 이런 윈도우의 크기를 저장하면서 매번 최댓값을 갱신합니다.

   여기서 주의할 점은 right는 조건 위반을 만났거나 배열 끝에 도달하면 멈추므로, 현재 valid한 윈도우의 길이는 right - left가 됩니다. right는 조건을 깨는 인덱스에 도달하거나 그 바로 다음 인덱스에 위치하므로 구간 크기를 셀 때 +1을 하지 않아도 됩니다.

4. 결과 반환:

   return maxBeauty;

   최대 길이가 maxBeauty에 저장되어 있으므로 이를 반환합니다.

정리:

• 이 코드는 정렬된 배열에서 투 포인터를 활용해 [left, right) 구간 내 원소들의 범위 차이가 2*k 이하가 되는 최대 구간 길이를 찾습니다.
• 모든 원소를 한 번씩만 처리하는 O(n) 시간 복잡도로 가능한 효율적인 방법입니다.
• 최종적으로, 구한 최대 길이가 문제에서 요구하는 최대 beauty 값을 의미합니다.

Approach 3: Line Sweep

• 12ms, 110.96MB
• Complexity
  • Let $n$ be the length of the input array nums and $maxValue$ be the maximum value in the array.
  • Time Complexity: $O(n + maxValue)$
  • Space Complexity: $O(maxValue)$

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        // If there's only one element, the maximum beauty is 1
        if (nums.size() == 1) return 1;

        int maxBeauty = 0;
        int maxValue = 0;

        // Find the maximum value in the array
        for (int num : nums) maxValue = max(maxValue, num);

        // Create an array to keep track of the count changes
        vector<int> count(maxValue + 1, 0);

        // Update the count array for each value's range [val - k, val + k]
        for (int num : nums) {
            count[max(num - k, 0)]++;  // Increment at the start of the range
            if (num + k + 1 <= maxValue)
                count[num + k + 1]--;  // Decrement after the range
        }

        int currentSum = 0;  // Tracks the running sum of counts
        // Calculate the prefix sum and find the maximum value
        for (int val : count) {
            currentSum += val;
            maxBeauty = max(maxBeauty, currentSum);
        }

        return maxBeauty;
    }
};

GPT

아래 코드는 “범위 업데이트”와 “누적 합(prefix sum)” 기법을 사용하여 최대 beauty 값을 효율적으로 계산하는 방법입니다. 이 방법은 각 수 num마다 [num - k, num + k] 구간을 모두 포함할 수 있는 “카운트 배열”을 만든 뒤, 어떤 값에서 가장 많은 수가 그 범위에 들어올 수 있는지 확인하는 원리로 작동합니다.

전체 아이디어:

1. 주어진 nums 배열의 각 원소 num에 대해, num을 기준으로 하는 [num - k, num + k] 범위 안에 들어갈 수 있는 모든 수들을 카운팅합니다. 이 범위는 “만약 우리가 [num, num+2k] 범위를 선택한다면 num 이 그 범위 안에 들어갈 수 있다”는 의미와 유사합니다.

2. 모든 수에 대해 이런 식으로 카운트한 뒤, 결국 가장 많은 원소가 한 번에 들어올 수 있는 값(정확히는, 그 값이 포함되는 최다 범위 수)을 찾으면, 그 값이 maximum beauty를 결정합니다.

단계별 설명:

1. 최대값 찾기:

   int maxValue = 0;
   for (int num : nums) maxValue = max(maxValue, num);

   주어진 nums에서 가장 큰 값을 찾습니다. 이 값은 카운트 배열의 크기를 결정하는데 사용됩니다.

2. 카운트 배열 생성:

   vector<int> count(maxValue + 1, 0);

   인덱스 i가 “값 i”를 의미하는 배열을 만듭니다.
   count[i]는 값 i에 도달하는 “누적 범위 변화량(difference)“를 기록하기 위한 용도입니다.
   여기서는 “차분 배열(difference array)” 기법을 사용할 것입니다.

3. 차분 배열 업데이트:

   for (int num : nums) {
       count[max(num - k, 0)]++;      // 범위 시작점에서 +1
       if (num + k + 1 <= maxValue)
           count[num + k + 1]--;      // 범위 끝난 다음 지점에서 -1
   }

   각 숫자 num에 대해 [num - k, num + k] 범위를 커버하도록, count 배열에 다음과 같이 표시합니다.

   • count[max(num - k, 0)]++: 이 위치에서부터 범위가 시작되므로 +1을 해줍니다. max(num - k, 0)는 범위가 음수가 되지 않도록 하는 처리입니다.
   • count[num + k + 1]--: 범위가 num + k에서 끝나므로, 그 다음 인덱스인 num + k + 1부터는 범위가 끝났음을 의미하는 -1을 해줍니다(단, num + k + 1이 maxValue를 넘어가지 않을 때만).

   이렇게 하면 count 배열은 단순히 범위 시작점에서 +1, 끝난 다음 지점에서 -1을 하는 “차분 배열”의 형태를 갖추게 됩니다.

4. 누적 합으로 실제 카운트 복원:

   int currentSum = 0;  
   for (int val : count) {
       currentSum += val;
       maxBeauty = max(maxBeauty, currentSum);
   }

   이제 count 배열에 누적 합을 취합니다. 이렇게 하면 원래 의도했던 것처럼 “각 값에서 몇 개의 [num-k, num+k] 범위가 겹치는지”를 알 수 있습니다.

   • currentSum는 현재 값에서 활성화되어 있는 범위의 수를 의미합니다.
   • 매 번 currentSum를 업데이트 할 때, maxBeauty를 갱신합니다.

   최종적으로 maxBeauty는 어떤 지점에서 가장 많은 범위가 겹쳤는지(즉, 가장 많은 원소를 동시에 포함시킬 수 있는 구간 선택의 최대값)가 됩니다.

5. 결과 반환:

   return maxBeauty;

   maxBeauty는 조건을 만족하는 최대 가능한 “beauty” 값을 반환합니다.

정리:

• 이 코드는 각 숫자마다 “적용 가능한 구간”을 차분 배열을 이용해 표시한 뒤, 누적 합을 통해 최종적으로 어떤 지점(값)에서 가장 많은 숫자를 커버할 수 있는지를 찾는 방식입니다.
• 정렬이나 이분 탐색 없이, O(n + maxValue) 정도의 시간에 문제를 해결할 수 있습니다 (maxValue가 크다면 비효율적일 수 있지만, 문제 조건에 따라 쓸 수 있는 전략입니다).
• maxBeauty가 결국 “최대 몇 개의 원소가 어떤 값 기준에서 [val, val+2k] 범위에 포함될 수 있는가”에 대한 답을 나타냅니다.