파이썬으로 남은 요소의 합이 k로 나누어떨어지도록 제거할 최소 길이의 부분 리스트 찾기

양의 정수로 이루어진 리스트 nums와 양의 정수 k가 주어졌다고 가정해 보겠습니다. 우리는 리스트에서 일부 요소를 삭제한 뒤, 남은 요소들의 합이 k로 나누어떨어지도록 만들어야 합니다. 이때 삭제할 수 있는 가장 짧은 연속 부분 리스트(빈 리스트도 허용)의 길이를 구하는 것이 목표입니다.

단, 전체 리스트를 통째로 삭제하는 것은 허용되지 않습니다. 또한 조건을 만족하는 부분 리스트가 존재하지 않는다면 -1을 반환해야 합니다.

예시

입력이 nums = [5, 8, 6, 3], k = 8이라고 해봅시다. 현재 요소들의 합은 5 + 8 + 6 + 3 = 22입니다. 여기서 길이가 1인 부분 리스트 [6]을 삭제하면 남은 합은 16이 되고, 16은 8로 나누어떨어집니다. 따라서 출력은 1입니다.

접근 방법

이 문제는 누적 합(prefix sum)과 모듈로 연산, 해시 맵을 함께 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '삭제할 구간의 합 mod k'가 전체 합의 나머지 값(rem)과 같아야 한다는 점입니다. 전체 풀이 과정은 다음과 같습니다.

rem := (리스트 전체 요소의 합 + k) mod k — 삭제해야 할 구간 합이 가져야 할 나머지 목표값
rem이 0이면 이미 전체 합이 k로 나누어떨어지므로 0을 반환
n := nums의 크기
presum := 누적 합, 초기값 0
mp := 딕셔너리, 키 0에 대해 -1 저장 (배열 시작 경계 처리용)
res := n으로 초기화
i를 0부터 n-1까지 반복:
- presum에 nums[i]를 더함
- m := (presum + k) mod k
- mp[m] := i 저장
- (m - rem + k) mod k가 mp에 존재하면, res를 res와 (i - mp[(m - rem + k) mod k]) 중 더 작은 값으로 갱신
반복 종료 후 res가 n이 아니면 res를 반환하고, 그렇지 않으면 -1을 반환

구현 예제

아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.

def solve(nums, k):
    rem = (sum(nums) + k) % k
    if rem == 0:
        return 0
    n, presum = len(nums), 0
    mp = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        m = (presum + k) % k
        mp[m] = i
        if (m - rem + k) % k in mp:
            res = min(res, i - mp[(m - rem + k) % k])
    return res if res != n else -1

nums = [5,8,6,3]
k = 8
print(solve(nums, k))

입력

[5,8,6,3], 8