[C++/LeetCode] Minimum Operations to Reduce X to Zero - using Sliding Window

Daily LeetCoding Challenge for June, Day 11.

 

문제

 

아이디어: Sliding Window

Sliding Window

특정 조건의 연속 합을 구할 때 고정된 사이즈의 윈도우를 이동시키며 O(N)으로 푸는 알고리즘

Two-Pointer 알고리즘과 달리 고정된 길이의 윈도우를 이동시킬 때 사용한다. 또한 정렬되어 있지 않아도 사용할 수 있다는 점에서 유용하다.

윈도우의 크기가 고정적이기 때문에 포인터가 2개일 필요도 없이 왼쪽 또는 오른쪽 포인터에 사이즈를 더하고 빼는 것으로 쉽게 윈도우의 범위를 구할 수 있다. 주로 Map을 이용해서 구현한다.

 

Sliding Window 알고리즘의 특성과 시간 복잡도가 O(N)인 이유

sliding window의 특징은 윈도우의 크기가 고정적이고 연속적인 합을 구할 때 사용한다는 것에 있다.

즉 사이즈가 w인 윈도우를 한칸 옆으로 옮기게 된다면 (w-1)칸은 겹치게 된다. 이는 정보가 중복된다는 것을 의미하므로 다시 계산할 필요가 없다는 뜻이 된다.

 

따라서 위와 같은 경우에서 구간합을 구한다면 3, 4, 5에 대한 값은 계산할 필요가 없이 left가 2, right가 6이라고 했을 때

이전합 - left

이전합 + right

으로 구할 수 있다. 즉 O(1)만으로 합을 구할 수 있다.

따라서 맨 처음에만 O(W)의 시간 복잡도가 소모되고 나머지 구간은 O(1)의 시간이 걸리므로 총 시간 복잡도가 O(N)이 되는 것이다.

 

 

이러한 sliding window를 문제에 적용해보자

문제에서 구해야 하는 것은 왼쪽과 오른쪽을 빼서 x를 0으로 만드는 것이다. 이를 반대로 말하면 왼쪽과 오른쪽을 적당히 더해서 x로 만드는 것과 같다.

하지만 이를 또 다른 관점에서 본다면 배열의 구간합이 (x - 배열의 합)이 되는 곳의 최대 길이를 구하는 것과 같다.

그렇다면 구간합 + 연속 + 고정된 윈도우 크기 라는 조건들이 모여 sliding window를 적용할 수 있게 된다.

 

 

구현

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(int iter: nums)
            sum += iter;
        
        int target = sum - x;
        int result = 0;
        int leftIndex = 0;
        
        int tempSum = 0;
        bool flag = false;
        
        // sliding window 알고리즘
        for(int rightIndex = 0;rightIndex < nums.size();rightIndex++)
        {
        // 오른쪽으로 이동시킴
            tempSum += nums[rightIndex];
            // 현재의 구간합이 구하고자 하는 합보다 커진 경우 leftIndex를 이동시킴
            while(leftIndex < rightIndex && tempSum > target)
            {
                tempSum -= nums[leftIndex];
                leftIndex++;
            }
            
            // target이 된 경우 result에 저장
            if (tempSum == target)
            {
                flag = true;
                result = max(result, rightIndex - leftIndex + 1);
            }
        }
        if (flag)
            return result;
        else
            return -1;
    }
};

 

참고