1658. Minimum Operations to Reduce X to Zero

• Hint를 보고 풀었던 문제.

풀이 1

• Array의 prefix + suffix를 찾는 것은 어렵기 때문에 문제를 반전시켜서 풀어야 한다.

• sub array의 element 합 subSum 이 전체 element의 합 sum 에서 x를 뺀 값과 같게 만드는 sub array들을 찾는다.

• 그리고 그 중에서 가장 길이가 긴 sub array를 찾는다. 전체 array 길이에서 해당 sub array의 길이를 빼면 결국 prefix + suffix의 최소 길이를 찾게 된다.

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int N = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int start = 0, end = 0, subSum = 0, result = -1;
        while (start < N) {
            if (subSum > sum - x) {
                // remove start element from sub array
                subSum -= nums[start];
                ++start;
            } else if (subSum < sum - x) {
                if (end == N) break;
                // add end element to sub array
                subSum += nums[end];
                ++end;
            } else {
                // get maximum length of sub array
                if (end - start > result) {
                    result = end - start;
                }
                // remove start element from sub array for next iteration
                subSum -= nums[start];
                ++start;
            }
        }
        // min ops = N - max sub arr length
        return result != -1? N - result : -1;
    }
};

풀이 2

• 이 문제가 어려운 이유는 array에서 prefix + suffix의 조합을 찾아내야 하기 때문이다.

• 만약 동일한 array 2개를 이어붙인다면 조건을 만족하는 최소 길이의 sub array를 찾는 문제로 바꿀 수 있다.

• 다만 sub array는 array 2개를 이어붙인 경계선에 걸쳐 있어야 하므로 시작점과 끝점이 경계선을 벗어나면 안된다. start <= N && end >= N - 1

• 또한 sub array의 길이가 array의 본래 길이 N 보다 커서도 안된다.

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int N = nums.size();
        int tN = N * 2;
        int start = 0, end = 0, sum = 0, result = tN;
        while (start < tN) {
            if (sum > x) {
                sum -= nums[start % N];
                ++start;
            } else if (sum < x) {
                if (end == tN) break;
                sum += nums[end % N];
                ++end;
            } else {
                if (start <= N && end >= N - 1) {
                    result = min(result, end - start);
                }
                sum -= nums[start % N];
                ++start;
            }
        }
        return result <= N? result : -1;
    }
};