[LeetCode] 1590. Make Sum Divisible by P

https://leetcode.com/problems/make-sum-divisible-by-p/description/?envType=daily-question&envId=2024-10-03

leetcode - Make Sum Divisible by P

문제 유형 : 부분합, 해시

문제 난이도 : Medium

 

문제

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

 

정수 배열 nums가 주어진다. 그 서브어레이를 제외한 나머지 요소들의 합이 p로 나누어 떨어지도록 가장 작은 서브어레이를 구하시오.

최소 길이를 반환하고, 불가능하면 -1을 반환하시오.

서브어레이(부분배열)은 배열 내에서 연속된 요소들의 블록입니다.

 

풀이

prefix[prefixSum] = (마지막으로 등장했던 인덱스)의 꼴로 해시맵 Prefix를 만든다.

우선, 총 합과 필요한 나머지를 구하고,

나머지가 0이면, 제거할 수가 없으므로 0을 반환한다.

그게 아니라면, 배열을 다시 한번 순차적으로 순회하면서, 매번 (0~i까지의 부분합 % p)값을 구해서 이전에 등장한 적 있다면, 길이를 구해서 최소 길이를 업데이트한다.

그리고, prefix[prefixSum]에 현재 인덱스 i를 덮어서 다음 순회 때 같은 부분합 %p의 값이 나오면, 더 짧은 거리를 구하도록 마지막 출현 인덱스를 업데이트한다.

 

한 번이라도 최소 길이가 업데이트된 적이 있다면, 그 최소길이를 반환하고, 그게 아니라면, -1을 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        long long sum = 0;
        for(auto &num : nums) sum += num;
        long long remainder = sum % p;
        
        if(remainder == 0) return 0;
        
        unordered_map<long, int> prefix;
        prefix[0] = -1;
        long long current = 0;
        int min_len = nums.size();
        
        for(int i = 0; i < nums.size(); ++i){
            current = (current + nums[i]) % p;
            long long target = (current - remainder + p) % p;
            if(prefix.find(target) != prefix.end()){
                min_len = min(min_len, i - prefix[target]);
            }
            prefix[current] = i;
        }
        
        return min_len < nums.size() ? min_len : -1;
    }
};