문제 링크

내 코드

해설 참고

Solution

Approach 1: Sorted Map

• 84ms, 113.02MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n \log k) \approx O(n)$
  • Space Complexity: $O(K) \approx O(1)$

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        // Map to maintain sorted frequency map of current window
        map<int, int> freq;
        int left = 0, right = 0;
        int n = nums.size();
        long long count = 0;  // Total count of valid subarrays

        while (right < n) {
            // Add current element to frequency map
            freq[nums[right]]++;

            // While window violates the condition |nums[i] - nums[j]| ≤ 2
            // Shrink window from left
            while (freq.rbegin()->first - freq.begin()->first > 2) {
                // Remove leftmost element from frequency map
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    freq.erase(nums[left]);
                }
                left++;
            }

            // Add count of all valid subarrays ending at right
            count += right - left + 1;
            right++;
        }

        return count;
    }
};

GPT

이 코드는 주어진 배열 nums에서, 모든 원소의 최대값과 최소값의 차이가 2 이하(|max - min| ≤ 2)인 연속 부분 배열(subarray)의 개수를 구하는 문제를 효율적으로 해결하는 방식을 보여줍니다.

핵심 아이디어:

• 슬라이딩 윈도우(Sliding Window) 기법을 사용합니다.
• 현재 윈도우(부분 배열) 내에 있는 원소들의 최솟값과 최댓값을 효율적으로 추적하기 위해 map<int,int>을 사용합니다.
  • map은 키를 기준으로 정렬되어 있으므로 map.begin()은 최소값, map.rbegin()은 최대값을 가진 원소의 iterator에 해당합니다.
• 윈도우 내 원소들의 최소값과 최대값 차이가 2 이하가 되도록 유지하면서, 그 윈도우로 만들 수 있는 모든 부분 배열의 개수를 누적합니다.

코드 동작 과정:

1. 변수 초기화:

   map<int,int> freq;  // 현재 윈도우 내 각 값의 빈도
   int left = 0, right = 0;  // 윈도우의 좌우 경계
   int n = nums.size();
   long long count = 0; 

2. 윈도우 확장:
   외부 while 루프는 right 포인터를 증가시키며, 윈도우를 오른쪽으로 확장합니다.

   while (right < n) {
       freq[nums[right]]++;

   현재 nums[right] 값을 freq 맵에 추가합니다. 이렇게 하면 윈도우 내 값들의 빈도가 갱신됩니다.

3. 조건 위배 시 윈도우 축소: 윈도우 내 최대값(freq.rbegin()->first)과 최소값(freq.begin()->first)의 차이를 검사합니다.

   while (freq.rbegin()->first - freq.begin()->first > 2) {
       // 조건 위배. 윈도우를 왼쪽에서 줄여나간다.
       freq[nums[left]]--;
       if (freq[nums[left]] == 0) {
           freq.erase(nums[left]);
       }
       left++;
   }

   만약 최대값 - 최소값 > 2라면, 조건(차이가 2 이하)을 만족할 때까지 left를 증가시켜 윈도우를 축소합니다. 이 과정에서 빈도가 0이 되는 값은 freq에서 제거합니다.

   결국 이 while 루프가 종료될 때, [left ... right] 구간은 |max-min| ≤ 2를 만족하는 최대 크기의 윈도우가 됩니다.

4. 부분 배열 개수 계산: 슬라이딩 윈도우 문제에서, 현재 [left ... right] 윈도우가 조건을 만족한다면, right를 고정했을 때 이 윈도우에 끝나는 모든 부분 배열들은 역시 조건을 만족합니다.

   count += right - left + 1;

   왜냐하면 left에서 right까지가 조건을 만족한다면, 이 내부에 끝나는 모든 짧은 부분 배열 (예: [right], [right-1, right], … [left, ..., right])도 조건을 만족하기 때문입니다.

   • 구체적으로, right 위치를 고정한 상태에서 왼쪽 경계를 left부터 right까지 변동시킬 수 있는데, 이미 left는 최대한 오른쪽에 밀착된 상태로 조건을 만족하는 최소 인덱스이므로 right - left + 1개의 부분 배열이 조건을 만족하게 됩니다.

5. 윈도우 확장 반복: right++를 하고 다시 조건을 확인하며 위 과정을 반복합니다. 최종적으로 count에는 조건을 만족하는 모든 연속 부분 배열의 개수가 합산됩니다.

6. 결과 반환:

   return count;

정리:

• 이 알고리즘은 슬라이딩 윈도우 + 정렬 맵을 활용하여 최대-최소 차이를 빠르게 확인하고, 윈도우를 유지하면서 조건을 만족하는 부분 배열의 개수를 효율적으로 계산합니다.
• 시간 복잡도는 O(n log n) 정도이며, 각 요소가 윈도우에 들어가고 나올 때 정렬 맵에 삽입/삭제되는 비용 때문입니다.
• 최종적으로 count는 모든 |max-min| ≤ 2 조건을 만족하는 부분 배열의 총 수가 됩니다.

Approach 2: Priority Queue

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

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int left = 0, right = 0;
        long long count = 0;  // Total count of valid subarrays

        // Min and max heaps storing indices, sorted by nums[index] values
        priority_queue<int, vector<int>, function<bool(int, int)>> minHeap(
            [&nums](int a, int b) { return nums[a] > nums[b]; });
        priority_queue<int, vector<int>, function<bool(int, int)>> maxHeap(
            [&nums](int a, int b) { return nums[a] < nums[b]; });

        while (right < nums.size()) {
            // Add current index to both heaps
            minHeap.push(right);
            maxHeap.push(right);

            // While window violates |nums[i] - nums[j]| ≤ 2 condition
            // Shrink window from left and remove outdated indices
            while (left < right &&
                   nums[maxHeap.top()] - nums[minHeap.top()] > 2) {
                left++;

                // Remove indices that are now outside window
                while (!maxHeap.empty() && maxHeap.top() < left) {
                    maxHeap.pop();
                }
                while (!minHeap.empty() && minHeap.top() < left) {
                    minHeap.pop();
                }
            }

            // Add count of all valid subarrays ending at right
            count += right - left + 1;
            right++;
        }

        return count;
    }
};

GPT

이 코드는 |nums[i] - nums[j]| ≤ 2 조건을 만족하는 연속 부분 배열의 총 개수를 구하는 또 다른 접근 방식입니다.
이전 코드에서는 map이나 정렬 구조를 사용했는데, 여기서는 최소값과 최대값을 효율적으로 추적하기 위해 **두 개의 힙(minHeap, maxHeap)**을 사용하고 있습니다.

핵심 아이디어:
슬라이딩 윈도우 기법을 사용하되, 현재 윈도우 [left, right] 안의 최소값과 최대값을 빠르게 얻기 위해 다음을 합니다.

• minHeap: nums값을 기준으로 최솟값을 빨리 가져올 수 있도록 하는 최소 힙 (여기서는 인덱스를 저장하지만, 비교 시 nums[index]를 통해 실제 값 비교).
• maxHeap: 최대값을 빨리 가져올 수 있도록 하는 최대 힙.

두 힙 모두 nums[index]의 값에 따라 비교하는 람다 함수를 사용하므로, nums를 직접 참조하여 힙에서 pop하는 순서가 결정됩니다.

동작 과정 상세:

1. 초기화:

   int left = 0, right = 0;
   long long count = 0;

   • left, right 두 포인터로 윈도우 경계를 나타냅니다.
   • count는 조건을 만족하는 부분 배열의 총 개수입니다.

2. 두 힙 초기화:

   priority_queue<int, vector<int>, function<bool(int,int)>> minHeap(
       [&nums](int a, int b){return nums[a] > nums[b];});
   priority_queue<int, vector<int>, function<bool(int,int)>> maxHeap(
       [&nums](int a, int b){return nums[a] < nums[b];});

   • minHeap: 인덱스 a, b를 비교할 때 nums[a] > nums[b]이면 a를 뒤로 보내므로 top에는 항상 nums값이 가장 작은 인덱스가 오게 됩니다.
   • maxHeap: 인덱스 a, b를 비교할 때 nums[a] < nums[b]이면 a가 뒤로 가므로 top에는 항상 nums값이 가장 큰 인덱스가 오게 됩니다.

   결국 minHeap.top()은 현재 윈도우에서 최소값을 주는 인덱스, maxHeap.top()은 최대값을 주는 인덱스를 가리킵니다.

3. 윈도우 확장 루프:

   while (right < nums.size()) {
       minHeap.push(right);
       maxHeap.push(right);

   • right를 이동시키며 새로운 원소를 윈도우에 추가합니다.
   • 새로 들어온 인덱스를 두 힙에 모두 추가합니다. 이제 minHeap.top()과 maxHeap.top()을 통해 윈도우 내 최소값과 최대값을 알 수 있습니다.

4. 조건 위배 시 윈도우 축소:

   while (left < right && nums[maxHeap.top()] - nums[minHeap.top()] > 2) {
       left++;
       
       // 윈도우가 left를 증가시켰으니, 힙에서 윈도우 범위 밖의 인덱스를 제거해야 함
       while (!maxHeap.empty() && maxHeap.top() < left) {
           maxHeap.pop();
       }
       while (!minHeap.empty() && minHeap.top() < left) {
           minHeap.pop();
       }
   }

   • 최대값(nums[maxHeap.top()])과 최소값(nums[minHeap.top()])의 차이가 2를 초과하면 조건 위배.
   • 윈도우 시작점을 한 칸 오른쪽으로 이동(left++)시킵니다.
   • 그리고 힙에서 left보다 작은 인덱스(윈도우 밖)을 모두 제거합니다. 이렇게 하면 힙에는 윈도우 내 유효한 인덱스만 남게 됩니다.
   • 이 과정을 조건이 만족될 때까지 반복합니다.

5. 부분 배열 개수 누적:

   count += right - left + 1;

   현재 right에서 끝나는 부분 배열 중, |nums[i] - nums[j]| ≤ 2를 만족하는 부분 배열의 개수를 더합니다.

   이유: left ~ right 범위가 조건을 만족한다면, right를 끝점으로 하는 부분 배열은 right-left+1개나 있으며, 이들 모두 조건을 만족합니다(윈도우의 left를 최대한 오른쪽으로 당겨 조건을 만족하는 최소 범위를 확보했기 때문).

6. right 포인터 이동:

   right++;

7. 반복: right가 nums.size()에 도달할 때까지 이 과정을 반복합니다.

결과 반환:

return count;

정리:

• 이 코드는 슬라이딩 윈도우 문제에서 최대값-최소값을 효율적으로 관리하기 위해 최소 힙, 최대 힙 두 개를 사용합니다.
• 윈도우를 확장하면서 조건을 만족하지 않으면 left를 이동해 윈도우를 축소하고, 힙에서 윈도우 범위 밖의 인덱스를 제거하는 방식으로 항상 조건을 만족하는 최대 범위를 유지합니다.
• 각 단계에서 윈도우 크기에 따라 조건을 만족하는 부분 배열의 수를 누적하여 최종 결과를 얻습니다.

Approach 3: Monotonic Deque

• 266ms, 122.30MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        // Monotonic deque to track maximum and minimum elements
        deque<int> maxQ, minQ;
        int left = 0;
        long long count = 0;

        for (int right = 0; right < nums.size(); right++) {
            // Maintain decreasing monotonic deque for maximum values
            while (!maxQ.empty() && nums[maxQ.back()] < nums[right]) {
                maxQ.pop_back();
            }
            maxQ.push_back(right);

            // Maintain increasing monotonic deque for minimum values
            while (!minQ.empty() && nums[minQ.back()] > nums[right]) {
                minQ.pop_back();
            }
            minQ.push_back(right);

            // Shrink window if max-min difference exceeds 2
            while (!maxQ.empty() && !minQ.empty() &&
                   nums[maxQ.front()] - nums[minQ.front()] > 2) {
                // Move left pointer past the element that breaks the condition
                if (maxQ.front() < minQ.front()) {
                    left = maxQ.front() + 1;
                    maxQ.pop_front();
                } else {
                    left = minQ.front() + 1;
                    minQ.pop_front();
                }
            }

            // Add count of all valid subarrays ending at current right pointer
            count += right - left + 1;
        }
        return count;
    }
};

GPT

이 코드는 주어진 배열 nums에서 모든 연속 부분 배열 중 최대값과 최소값의 차가 2 이하인 부분 배열들의 개수를 구합니다. 이를 효율적으로 처리하기 위해 모노토닉 데크(Monotonic Deque) 를 사용하고 있습니다.

핵심 아이디어:

• 최대값을 유지하는 데크(maxQ)와 최소값을 유지하는 데크(minQ) 두 개를 유지합니다.
• 두 데크 모두 윈도우(현재 고려하고 있는 부분 배열) 범위 내에서 해당하는 최댓값 및 최솟값을 효율적으로 파악할 수 있게 합니다.
• 데크는 인덱스를 저장하며, maxQ는 내림차순으로 정렬(즉, 맨 앞이 최대값 인덱스), minQ는 오름차순으로 정렬(맨 앞이 최소값 인덱스)됩니다.

구체적 동작 과정:

1. 변수 초기화:

   deque<int> maxQ, minQ;  
   int left = 0;  
   long long count = 0;

   • maxQ: 현재 윈도우에서 최댓값 인덱스를 빠르게 접근하기 위한 데크. 값이 내림차순 유지.
   • minQ: 현재 윈도우에서 최솟값 인덱스를 빠르게 접근하기 위한 데크. 값이 오름차순 유지.
   • left: 윈도우의 왼쪽 포인터
   • count: 조건을 만족하는 부분 배열의 개수를 누적하기 위한 변수

2. 윈도우 확장 반복문:

   for (int right = 0; right < nums.size(); right++) {
       // 새로운 요소 nums[right]를 윈도우에 포함

   • right를 늘려가며 윈도우의 오른쪽 범위를 확장합니다.

3. maxQ 업데이트:

   while (!maxQ.empty() && nums[maxQ.back()] < nums[right]) {
       maxQ.pop_back();
   }
   maxQ.push_back(right);

   • maxQ는 값이 큰 인덱스가 앞쪽에 오게끔 유지합니다.
   • nums[right]가 기존 maxQ의 뒤쪽 값보다 크면 그 값들은 더 이상 최대값 후보가 될 수 없으므로 pop_back()으로 제거합니다.
   • 그런 뒤 right 인덱스를 삽입합니다.
   • 결과적으로 maxQ.front()는 현재 윈도우 내 최댓값의 인덱스를 가리킵니다.

4. minQ 업데이트:

   while (!minQ.empty() && nums[minQ.back()] > nums[right]) {
       minQ.pop_back();
   }
   minQ.push_back(right);

   • minQ는 값이 작은 인덱스가 앞쪽에 오게끔 유지합니다.
   • nums[right]가 기존 minQ의 뒤쪽 값보다 작으면, 더 큰 값들은 최소값 후보에서 밀려나므로 pop_back()을 통해 제거.
   • 그런 뒤 right를 삽입.
   • minQ.front()는 현재 윈도우 내 최솟값의 인덱스를 가리킵니다.

5. 조건 위반 시 윈도우 축소:

   while (!maxQ.empty() && !minQ.empty() && 
          nums[maxQ.front()] - nums[minQ.front()] > 2) {
       if (maxQ.front() < minQ.front()) {
           left = maxQ.front() + 1;
           maxQ.pop_front();
       } else {
           left = minQ.front() + 1;
           minQ.pop_front();
       }
   }

   • 현재 윈도우에서 maxQ.front()는 최대값 인덱스, minQ.front()는 최소값 인덱스를 의미합니다.
   • nums[maxQ.front()] - nums[minQ.front()] > 2이면 조건을 어기는 것이므로, 윈도우를 축소해야 합니다.
   • 축소 시, 조건을 깨뜨리는 인덱스를 포함하는 쪽(최대값이 더 왼쪽에 있으면 maxQ쪽 기준, 최소값이 더 왼쪽이면 minQ쪽 기준)으로 left를 조정합니다.
   • 해당 인덱스를 데크에서 제거하여 윈도우 범위를 재설정합니다.

   이 과정으로 인해 left가 이동하며 윈도우 내 |max - min| ≤ 2 조건을 다시 만족하게 됩니다.

6. 유효한 윈도우 기반 부분 배열 개수 누적:

   count += right - left + 1;

   • 현재 right 위치에서 끝나는 부분 배열들 중, [left ... right] 범위는 조건을 만족합니다.
   • 이 윈도우 내에서 right를 끝점으로 하는 부분 배열은 right - left + 1개 존재합니다.
   • 따라서 이를 count에 더합니다.

7. 반복:

   • right를 증가시키며 모든 인덱스에 대해 윈도우를 확장하고, 필요하면 축소하면서 모든 조건 만족 부분 배열을 카운트합니다.

8. 결과 반환:

   return count;

정리:

• 이 방법은 최대값과 최소값을 O(1)에 접근하기 위해 두 개의 모노토닉 데크를 사용하는 슬라이딩 윈도우 접근법입니다.
• 각 확장 단계에서 새로운 원소를 데크에 삽입하여 최대/최소를 갱신하고, 조건을 어기는 경우 데크를 참고해 left를 이동하여 윈도우를 축소합니다.
• 최종적으로, 모든 조건을 만족하는 부분 배열의 개수를 빠르고 효율적으로 계산할 수 있습니다.

Approach 4: Optimized Two Pointer

• 75ms, 111.75MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int right = 0, left = 0;
        int curMin, curMax;
        long long windowLen = 0, total = 0;

        // Initialize window with the first element
        curMin = curMax = nums[right];

        for (right = 0; right < nums.size(); right++) {
            // Update min and max for the current window
            curMin = min(curMin, nums[right]);
            curMax = max(curMax, nums[right]);

            // If window condition breaks (diff > 2)
            if (curMax - curMin > 2) {
                // Add subarrays from the previous valid window
                windowLen = right - left;
                total += (windowLen * (windowLen + 1) / 2);

                // Start a new window at the current position
                left = right;
                curMin = curMax = nums[right];

                // Expand left boundary while maintaining the condition
                while (left > 0 && abs(nums[right] - nums[left - 1]) <= 2) {
                    left--;
                    curMin = min(curMin, nums[left]);
                    curMax = max(curMax, nums[left]);
                }

                // Remove overcounted subarrays if left boundary expanded
                if (left < right) {
                    windowLen = right - left;
                    total -= (windowLen * (windowLen + 1) / 2);
                }
            }
        }

        // Add subarrays from the final window
        windowLen = right - left;
        total += (windowLen * (windowLen + 1) / 2);

        return total;
    }
};

GPT

이 코드는 |max - min| ≤ 2 조건을 만족하는 연속 부분 배열들의 총 개수를 세는 또 다른 방식의 구현입니다. 기본적인 아이디어는 “조건이 깨지기 전까지의 윈도우”를 누적해서 계산하는 방법이지만, 구현 과정이 조금 복잡합니다. 전반적으로 슬라이딩 윈도우/투 포인터 아이디어를 사용하지만, 조건이 깨질 때마다 “기존 윈도우의 부분 배열 개수”를 계산 후 total에 더하고, 새 윈도우를 시작하는 방식을 취하고 있습니다.

코드 상세 설명:

1. 변수 초기화:

   int right = 0, left = 0;
   int curMin, curMax;
   long long windowLen = 0, total = 0;

   • right, left는 윈도우 양 끝을 나타내는 인덱스.
   • curMin, curMax는 현재 윈도우에서의 최소값, 최대값.
   • windowLen는 현재 윈도우 길이, total은 누적 결과.

   초기 윈도우는 첫 번째 원소로 시작하지만, 이 아래 코드에서는 curMin, curMax를 초기화 한 뒤 바로 for문을 돌기 때문에 사실상 첫 루프에서 초기화가 완료됩니다.

2. 윈도우 확장 루프:

   for (right = 0; right < nums.size(); right++) {
       curMin = min(curMin, nums[right]);
       curMax = max(curMax, nums[right]);

   매 right 증가 시, 현재 윈도우 [left...right]에 대해 curMin, curMax를 갱신합니다.

3. 조건 검사 및 윈도우 재설정:

   if (curMax - curMin > 2) {
       // 조건을 깨는 경우:
       // 지금까지의 유효한 윈도우 길이 = (right - 1) - left + 1 = right - left
       // right는 이미 조건을 깬 원소를 포함했기 때문
       windowLen = right - left;
       total += (windowLen * (windowLen + 1) / 2);
       
       // 새로운 윈도우 시작: 현재 위치(right)에서 다시 시작
       left = right;
       curMin = curMax = nums[right];
   
       // 여기서 left를 뒤로 이동시키며 조건을 다시 만족할 수 있는지 확인
       // 이 부분은 배열의 특정 패턴을 감안한 조정으로 보이며,
       // 조건을 깨는 지점에서 다시 최대한 뒤로 확장해볼 수 있는지 시도하는 것 같다.
       while (left > 0 && abs(nums[right] - nums[left - 1]) <= 2) {
           left--;
           curMin = min(curMin, nums[left]);
           curMax = max(curMax, nums[left]);
       }
   
       // 만약 left를 뒤로 확장했다면, 그에 따라 overcounted(너무 많이 더한) 부분 배열을 빼준다.
       // 새로 잡은 윈도우 길이를 계산하고 그만큼 total에서 빼주는 과정.
       if (left < right) {
           windowLen = right - left;
           total -= (windowLen * (windowLen + 1) / 2);
       }
   }

   여기서 로직이 다소 복잡한데, 정리하자면:

   • curMax - curMin > 2일 때, 지금까지 [left...right-1] 구간은 조건을 만족하는 최대 윈도우였다.
   • 해당 윈도우로 만들 수 있는 부분 배열 개수는 windowLen * (windowLen + 1) / 2 형태로 계산(길이가 L이면 부분 배열 수는 L*(L+1)/2).
   • 이를 total에 더한 뒤, 현재 right 위치에서 윈도우를 다시 시작한다(left = right).
   • 그 후, 다시 left를 왼쪽으로 확장할 수 있는지 체크하는데, 이는 현재 원소와 인접 이전 원소들 중 조건을 만족하는 범위가 더 넓어질 수 있는지 확인하는 과정이다.
   • 만약 left를 뒤로 당겨 확장했다면, 그만큼 total에서 과도하게 더한 부분 배열 수를 빼준다. 이것은 이전에 더한 부분 중 일부가 이제는 새로운 윈도우에 포함되어 이중으로 계산되는 것을 방지하기 위함이다.

   이 과정은 문제를 해결하기 위한 특정한 최적화나 패턴 인식에 의한 것으로, 직관적으로 다가가기 어렵지만, 결국 “조건 깨지기 전까지의 구간 계산” → “새 윈도우 설정” → “확장 가능하다면 확장” → “과잉 계산 조정” 과정을 수행합니다.

4. 루프 종료 후 남은 윈도우 처리:

   windowLen = right - left;
   total += (windowLen * (windowLen + 1) / 2);

   모든 원소를 처리한 뒤에도 마지막으로 유효한 윈도우 [left ... right-1]가 남아 있으니, 그 길이에 따른 부분 배열 수를 total에 더해줍니다.

5. 결과 반환:

   return total;

정리:
이 코드는 조건을 깨기 전까지 윈도우를 확장하고, 조건이 깨지면 지금까지의 윈도우로 가능한 부분 배열 수를 계산하여 total에 더한 뒤, 새로운 윈도우를 시작하는 방식을 반복합니다. 그 과정에서 left 포인터를 다시 뒤로 확장해 조건을 만족하는 더 큰 윈도우를 만들 수 있으면 만들고, 이로 인한 중복 계산을 조정하는 복잡한 로직을 포함합니다.

결국 최종 결과인 total은 모든 조건을 만족하는 연속 부분 배열의 총 개수가 됩니다. 다른 솔루션들에 비해 구현이 상당히 복잡하고 비직관적이나, 같은 문제를 해결하는 또 하나의 접근 방식으로 볼 수 있습니다.