파이썬으로 합이 목표값과 같은 비중첩 부분 배열의 최대 개수 찾기

문제 설명

배열 nums와 목표값 target이 주어졌다고 가정해 보겠습니다. 이때 각 부분 배열의 원소 합이 정확히 target과 같으면서, 서로 겹치지 않고 비어 있지 않은 부분 배열의 최대 개수를 구하는 것이 과제입니다.

예를 들어 입력이 nums = [3,2,4,5,2,1,5], target = 6이라면 출력은 2가 됩니다. 합이 6인 부분 배열 [2,4]와 [1,5], 이렇게 두 개를 찾을 수 있기 때문입니다.

접근 방법: 누적합(Prefix Sum) 활용

이 문제는 누적합(prefix sum)과 집합(set)을 이용하면 선형 시간에 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 현재까지의 누적합을 temp라고 할 때, 이전에 기록해 둔 누적합 중 temp - target이 존재한다면 그 지점부터 현재 위치까지의 부분 배열의 합이 정확히 target이라는 의미입니다. 부분 배열이 서로 겹치면 안 되므로, 하나를 찾을 때마다 집합을 현재 누적합만 담은 새 집합으로 초기화하여 이후 탐색이 해당 위치부터 새롭게 시작되도록 합니다.

알고리즘 단계

• t := 0만 포함하는 새로운 집합 생성
• temp := 0 (누적합 저장 변수)
• ans := 0 (결과 카운터)
• nums의 각 원소 i에 대해 반복:
  • temp := temp + i
  • prev := temp - target
  • 만약 prev가 t에 존재하면:
    • ans := ans + 1
    • t := temp만 포함하는 새로운 집합으로 초기화 (겹침 방지)
  • 그렇지 않으면:
    • t에 temp 추가
• ans 반환

구현 예제

def solve(nums, target):
    t = set([0])
    temp = 0
    ans = 0
    for i in nums:
        temp += i
        prev = temp - target
        if prev in t:
            ans += 1
            t = set([temp])
        else:
            t.add(temp)
    return ans

nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

실행 결과

2

동작 과정 상세 분석

위 예제가 어떻게 동작하는지 단계별로 살펴보겠습니다.

최종적으로 ans = 2가 반환됩니다. 이는 합이 6인 두 개의 비중첩 부분 배열 [2,4]와 [1,5]를 성공적으로 찾았음을 의미합니다.

시간 및 공간 복잡도

배열을 한 번만 순회하고, 각 단계에서 집합의 삽입·조회 연산은 평균 O(1)이므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 최악의 경우 모든 누적합을 집합에 저장해야 하므로 역시 O(n)입니다.