문제 개요
숫자로 이루어진 리스트 nums와 목표 값 target이 주어졌을 때, 원소들의 합이 target과 같아지는 연속된 부분 리스트(sublist)의 개수를 구하는 문제입니다.
예를 들어 nums = [3, 0, 3], target = 3이라면, 합이 3이 되는 부분 리스트는 [3], [3, 0], [0, 3], [3]으로 총 4개이므로 결과값은 4가 됩니다.
해결 접근 방식
모든 부분 리스트를 일일이 확인하는 브루트 포스 방식은 O(n²) 이상의 시간이 걸립니다. 반면 누적 합(prefix sum)과 해시맵을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 인덱스 i까지의 누적 합을 s라고 할 때, 이전 어느 시점까지의 누적 합이 s - target과 같다면, 그 시점 다음부터 i까지의 부분 리스트의 합은 정확히 target이 됩니다. 따라서 각 누적 합이 등장한 횟수를 해시맵에 기록해 두면, 현재 위치에서 끝나는 유효한 부분 리스트의 개수를 즉시 알 수 있습니다.
알고리즘 단계
- 누적 합 등장 횟수를 저장할 빈 맵(딕셔너리) temp를 준비하고, temp[0] := 1로 초기화합니다.
- 현재 누적 합 s := 0, 정답 카운터 ans := 0으로 초기화합니다.
- 리스트의 각 원소를 순회하며 다음을 반복합니다.
- s := s + nums[i] (누적 합 갱신)
- comp := s - target (찾아야 할 이전 누적 합)
- 만약 comp가 temp에 존재하면, ans := ans + temp[comp]
- temp[s] := temp[s] + 1 (현재 누적 합 기록)
- 순회가 끝나면 ans를 반환합니다.
예제 코드
from collections import defaultdict
class Solution:
def solve(self, nums, target):
temp = defaultdict(int)
temp[0] = 1
s = 0
ans = 0
for i in range(len(nums)):
s += nums[i]
comp = s - target
if comp in temp:
ans += temp[comp]
temp[s] += 1
return ans
ob = Solution()
nums = [3, 0, 3]
target = 3
print(ob.solve(nums, target))입력
[3, 0, 3], 3
출력
4
동작 과정 살펴보기
입력 [3, 0, 3], target = 3일 때 알고리즘이 어떻게 진행되는지 단계별로 확인해 보겠습니다.
- i = 0: s = 3, comp = 0 → temp[0] = 1이므로 ans = 1, temp = {0: 1, 3: 1}
- i = 1: s = 3, comp = 0 → temp[0] = 1이므로 ans = 2, temp = {0: 1, 3: 2}
- i = 2: s = 6, comp = 3 → temp[3] = 2이므로 ans = 4, temp = {0: 1, 3: 2, 6: 1}
최종적으로 ans = 4가 반환되며, 이는 [3], [3, 0], [0, 3], [3] 네 개의 부분 리스트에 해당합니다.
복잡도 분석
리스트를 한 번만 순회하고 각 단계에서 해시맵 연산은 평균 O(1)이므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 누적 합을 저장하는 해시맵 때문에 최악의 경우 O(n)입니다.