1590. Make Sum Divisible by P

Problem : https://leetcode.com/problems/make-sum-divisible-by-p

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:39:33

 

---

 

문제 설명

 

 

양의 정수로 구성된 배열 nums가 주어졌을때, 남은 원소의 합이 p로 나누어지는 가장 작은 부분배열(길이가 0일 수도 있다)을 제거하도록 한다. 전체 배열을 제거하는 것은 허락되지 않는다.

 

그 가장 작은 부분배열의 길이를 반환하라. 만약 불가능하다면 -1을 반환하라.

 

부분배열은 배열의 연속된 원소로 이루어진 구간을 의미한다. 

---

 

풀이

 

부분합으로 풀어야하나... DP로 풀어야하나... 꽤 고민하다가 DP를 선택했고, 가차없이 틀렸다. 부분합으로 풀이해보도록 하자.

 

우리는 조금 다른 특수한 부분합을 구할 것이다. 합을 구하는 건 동일하나, p mod, 즉 p로 나누었을 때의 나머지를 저장할 것이다.

 

이제 다음으로, 제거해야 할 부분배열의 의미를 조금 더 고찰해 보자.

• 부분배열을 제거함으로써 남은 원소의 합이 p로 나누어진다는 의미를 분해해 보면,
• 현재 전체 원소의 나머지가 a일때
• 부분배열의 합(즉 구간합 - sums[j] - sums[i]) 역시 나머지가 a임을 의미한다.
• 따라서 전체에서 부분배열을 뺄 때 나머지 연산이 0이 되고, 남은 원소들의 합은 P로 나눠지게 된다.

즉 남은 원소들의 합이 a가 되는 전체 구간합 후보를 구하여, 그 중 제일 짧은 값을 반환해볼 수 있겠다.

 

 

 

풀이 코드

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:        
        sums = [0]
        for n in nums :
            sums.append((sums[-1] + n) % p)
        
        if sums[-1] == 0 :
            return 0

        target = sums[-1]
        last = {0 : 0}
        result = len(nums)

        for i in range(1, len(nums)+1) :
            t = (sums[i] - target) % p
            if t in last :
                result = min(result, i - last[t])
            last[sums[i]] = i

        return result if result < len(nums) else -1