Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀기: 절대 차이가 제한 이하인 가장 긴 연속 부분 배열 찾기

문제 개요

정수 배열 nums와 정수 limit가 주어졌을 때, 부분 배열 내 임의의 두 원소 간 절대 차이가 주어진 제한(limit)보다 작거나 같은 조건을 만족하는 가장 긴 비어 있지 않은 연속 부분 배열의 길이를 구하는 문제입니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

nums = [8, 2, 4, 7], limit = 4

이 경우 정답은 2입니다. 모든 가능한 부분 배열을 확인해 보면 그 이유를 알 수 있습니다.

  • [8] → |8 - 8| = 0 ≤ 4 ✅
  • [8, 2] → |8 - 2| = 6 > 4 ❌
  • [8, 2, 4] → |8 - 2| = 6 > 4 ❌
  • [8, 2, 4, 7] → |8 - 2| = 6 > 4 ❌
  • [2] → |2 - 2| = 0 ≤ 4 ✅
  • [2, 4] → |2 - 4| = 2 ≤ 4 ✅
  • [2, 4, 7] → |2 - 7| = 5 > 4 ❌
  • [4] → |4 - 4| = 0 ≤ 4 ✅
  • [4, 7] → |4 - 7| = 3 ≤ 4 ✅
  • [7] → |7 - 7| = 0 ≤ 4 ✅

조건을 만족하는 가장 긴 부분 배열의 길이는 [2, 4] 또는 [4, 7]처럼 2입니다.

접근 방법: 슬라이딩 윈도우 + 단조 데크(Monotonic Deque)

모든 부분 배열을 일일이 검사하면 시간 복잡도가 O(n²) 이상으로 늘어나 비효율적입니다. 대신 슬라이딩 윈도우 기법과 두 개의 단조 데크(deque)를 활용하면 O(n) 시간에 문제를 해결할 수 있습니다.

  • maxD: 현재 윈도우 구간에서 최댓값 후보들을 내림차순으로 유지하는 데크
  • minD: 현재 윈도우 구간에서 최솟값 후보들을 오름차순으로 유지하는 데크

핵심 아이디어는 다음과 같습니다. 어떤 부분 배열의 최댓값과 최솟값의 차이가 limit 이하라면, 그 배열 내 임의의 두 원소의 차이도 반드시 limit 이하입니다. 따라서 maxD.front() - minD.front() <= limit를 만족하는 한 윈도우를 계속 확장하고, 조건이 깨지면 왼쪽 끝을 줄여 나갑니다.

알고리즘 단계

  1. 결괏값 ret = 0, 윈도우 포인터 i = 0(오른쪽 끝), j = 0(왼쪽 끝)으로 초기화합니다.
  2. 두 개의 빈 데크 maxD, minD를 선언합니다.
  3. 배열을 순회하며 각 원소 nums[i]에 대해:
    • maxD의 뒤쪽 값이 nums[i]보다 작으면 pop_back()으로 제거합니다(내림차순 유지).
    • minD의 뒤쪽 값이 nums[i]보다 크면 pop_back()으로 제거합니다(오름차순 유지).
    • nums[i]를 두 데크 뒤에 삽입합니다.
  4. maxD.front() - minD.front() > k인 동안:
    • nums[j]가 maxD.front()와 같으면 maxD에서 앞 원소를 제거합니다.
    • nums[j]가 minD.front()와 같으면 minD에서 앞 원소를 제거합니다.
    • j를 증가시켜 윈도우 왼쪽 끝을 축소합니다.
  5. 현재 윈도우 길이 i - j + 1과 ret 중 큰 값을 저장합니다.
  6. 순회가 끝나면 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubarray(vector<int>& nums, int k) {
      int ret = 0;
      int i = 0;
      int j = 0;
      deque<int> maxD;
      deque<int> minD;
      int n = nums.size();
      for (int i = 0; i < n; i++) {
         while (!maxD.empty() && maxD.back() < nums[i])
            maxD.pop_back();
         while (!minD.empty() && minD.back() > nums[i])
            minD.pop_back();
         maxD.push_back(nums[i]);
         minD.push_back(nums[i]);
         while (maxD.front() - minD.front() > k) {
            if (nums[j] == maxD.front())
               maxD.pop_front();
            if (nums[j] == minD.front())
               minD.pop_front();
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {7,8,2,4};
   cout << (ob.longestSubarray(v, 4));
}

입력

{7,8,2,4}, 4

출력

2

복잡도 분석

  • 시간 복잡도: O(n) — 각 원소는 데크에 최대 한 번 삽입되고 한 번 제거되므로 전체 연산 횟수는 배열 길이에 비례합니다.
  • 공간 복잡도: O(n) — 최악의 경우 두 데크가 배열 전체 크기만큼 공간을 사용할 수 있습니다.

이처럼 단조 데크를 활용한 슬라이딩 윈도우는 '구간 최댓값/최솟값'을 상수 시간에 추적할 수 있게 해주는 강력한 패턴으로, 유사한 문제(슬라이딩 윈도우 최댓값 등)에도 폭넓게 응용됩니다.