파이썬으로 합이 k가 되는 겹치지 않는 두 부분 리스트의 최소 길이 합 구하기

문제 설명

숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 보겠습니다. 이때 합이 k가 되는 서로 겹치지 않는(non-overlapping) 두 개의 부분 리스트를 찾아 그 길이의 합을 구해야 합니다. 가능한 조합이 여러 개라면 가장 짧은 두 부분 리스트를 선택해야 하며, 조건을 만족하는 답이 없다면 -1을 반환합니다.

예를 들어 입력이 nums = [7, 10, -2, -1, 4, 3], k = 7이라면 출력은 3이 됩니다. [7]과 [4, 3]을 선택하면 되는데, [10, -2, -1] 역시 합이 7이지만 길이가 더 길기 때문에 선택하지 않습니다.

접근 방법

모든 경우를 완전 탐색하면 비효율적이므로, 접두사(prefix) 배열과 접미사(suffix) 배열을 활용하면 선형 시간에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• prefix[i]: 인덱스 0부터 i까지 범위에서 합이 target이 되는 부분 리스트의 최소 길이
• suffix[i]: 인덱스 i부터 끝까지 범위에서 합이 target이 되는 부분 리스트의 최소 길이
• 각 분할 지점 i에 대해 prefix[i] + suffix[i + 1]의 최솟값이 곧 정답이 됩니다.

특정 합을 가지는 부분 리스트를 빠르게 찾기 위해 누적합(prefix sum)과 해시 맵을 함께 사용합니다. 현재까지의 누적합이 s일 때, s - target이 이전에 등장한 적이 있다면 그 위치 바로 다음부터 현재 위치까지의 부분 리스트 합이 정확히 target이 됩니다.

알고리즘 단계

1. N := A의 크기로 설정
2. prefix := 크기가 N인 배열을 무한대(INF)로 초기화
3. last := {0: -1} 형태의 맵 생성
4. s := 0으로 초기화
5. i를 0부터 N-1까지 순회:
   • s := s + A[i]
   • prefix[i] := i - last[s - target] (존재하지 않으면 -INF)
   • last[s] := i 저장
6. i를 1부터 N-1까지 순회하며 prefix[i] := min(prefix[i], prefix[i - 1])로 갱신하여 누적 최솟값 유지
7. suffix := 크기가 N인 배열을 무한대(INF)로 초기화
8. last := {0: N} 형태의 맵 생성
9. s := 0으로 초기화
10. i를 N-1부터 0까지 역순으로 순회:
    • s := s + A[i]
    • suffix[i] := last[s - target] - i (존재하지 않으면 INF)
    • last[s] := i 저장
11. i를 N-2부터 0까지 역순으로 순회하며 suffix[i] := min(suffix[i], suffix[i + 1])로 갱신
12. ans := 모든 i에 대해 prefix[i] + suffix[i + 1]의 최솟값
13. ans가 무한대보다 작으면 ans를, 그렇지 않으면 -1을 반환

구현 예제

class Solution:
    def solve(self, A, target):
        INF = float("inf")
        N = len(A)
        prefix = [INF] * N
        last = {0: -1}
        s = 0
        for i in range(N):
            s += A[i]
            prefix[i] = i - last.get(s - target, -INF)
            last[s] = i
        for i in range(1, N):
            prefix[i] = min(prefix[i], prefix[i - 1])
        suffix = [INF] * N
        last = {0: N}
        s = 0
        for i in range(N - 1, -1, -1):
            s += A[i]
            suffix[i] = last.get(s - target, INF) - i
            last[s] = i
        for i in range(N - 2, -1, -1):
            suffix[i] = min(suffix[i], suffix[i + 1])
        ans = min(prefix[i] + suffix[i + 1] for i in range(N - 1))
        return ans if ans < INF else -1

ob = Solution()
nums = [7, 10, -2, -1, 4, 3]
k = 7
print(ob.solve(nums, k))

입력

[7, 10, -2, -1, 4, 3], 7

출력

3

동작 원리 살펴보기

입력 [7, 10, -2, -1, 4, 3]에서 target이 7일 때, 왼쪽 스캔에서는 [7](길이 1)을, 오른쪽 스캔에서는 [4, 3](길이 2)을 찾습니다. 두 리스트가 서로 겹치지 않으므로 길이의 합은 1 + 2 = 3이 되며, 이것이 가능한 최솟값입니다.

복잡도 분석

시간 복잡도: O(N) — 리스트를 앞방향과 뒷방향으로 각각 한 번씩만 순회합니다.
공간 복잡도: O(N) — prefix, suffix 배열과 해시 맵에 추가 공간이 필요합니다.