Python으로 배열을 같은 합의 부분 배열로 나누기: 가능한 모든 합계 값 찾기

정수로 이루어진 배열 A가 주어졌을 때, 어떤 값 sum[i]를 기준으로 배열 전체를 합이 sum[i]와 동일한 연속된 부분 배열들로 나눌 수 있다면, 그러한 조건을 만족하는 모든 합계 값을 찾아야 합니다. 만약 어떤 합으로도 배열을 균등하게 나눌 수 없다면 -1을 반환합니다.

문제 예시

예를 들어 입력이 A = [2, 4, 2, 2, 2, 4, 2, 6]이라면 출력은 [6, 8, 12]가 됩니다. 이 배열은 합이 6, 8, 12인 부분 배열들로 각각 나눌 수 있기 때문입니다.

합이 6일 때: {2, 4}, {2, 2, 2}, {4, 2}, {6}
합이 8일 때: {2, 4, 2}, {2, 2, 4}, {2, 6}
합이 12일 때: {2, 4, 2, 2, 2}, {4, 2, 6}

해결 접근 방법

이 문제의 핵심 아이디어는 두 가지입니다. 첫째, 누적합(prefix sum)을 미리 계산해 두면 임의의 지점까지의 구간 합을 빠르게 확인할 수 있습니다. 둘째, 배열 전체의 합 S를 k개의 동일한 합을 가진 구간으로 나누려면 반드시 S의 약수여야 한다는 점입니다. 따라서 S의 약수만 후보로 삼아 검증하면 효율적으로 답을 구할 수 있습니다.

알고리즘 단계

n := 배열 a의 크기
table := 크기가 n이고 0으로 채워진 배열 (누적합 저장용)
table[0] := a[0]
i를 1부터 n-1까지 순회하며 table[i] := a[i] + table[i-1] 계산
S := table[n-1], 즉 배열 전체의 합
my_map := 새로운 맵을 만들고, 모든 누적합 table[i]를 키로 등록
answer := 결과를 저장할 새로운 집합(set)
i를 1부터 √S의 정수 부분 + 1까지 순회하며:
- S mod i == 0이라면 i는 S의 약수이므로 두 가지 경우를 검사
  - part_1 := i 인 경우, part_1부터 S까지 part_1씩 증가하며 해당 값이 my_map에 모두 존재하는지 확인 → 존재하고 part_1 ≠ S라면 answer에 추가
  - part_2 := S // i 인 경우, 마찬가지로 part_2부터 S까지 part_2씩 증가하며 존재 여부 확인 → 존재하고 part_2 ≠ S라면 answer에 추가
answer의 크기가 0이면 -1 반환
그렇지 않으면 answer 반환

여기서 my_map에 누적합을 미리 등록해 두는 이유는, 합이 part_1 또는 part_2인 구간들이 배열을 정확히 잘라낼 수 있으려면 그 배수 지점(part_1, 2×part_1, 3×part_1, ...)마다 누적합이 존재해야 하기 때문입니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

from math import sqrt
def find_sum(a) :
    n = len(a)
    table = [0] * n
    table[0] = a[0]
    for i in range(1, n) :
        table[i] = a[i] + table[i - 1]
    S = table[n - 1]
    my_map = {}
    for i in range(n) :
        my_map[table[i]] = 1
    answer = set()
    for i in range(1, int(sqrt(S)) + 1) :
        if (S % i == 0) :
            is_present = True;
            part_1 = i
            part_2 = S // i
            for j in range(part_1 , S + 1, part_1) :
                if j not in my_map :
                    is_present = False
                    break
            if (is_present and part_1 != S) :
                answer.add(part_1)
            is_present = True
            for j in range(S // i , S + 1 , S // i) :
                if j not in my_map:
                    is_present = False;
                    break
            if (is_present and part_2 != S) :
                answer.add(part_2)
    if(len(answer) == 0) :
        return -1
    return answer
a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))

입력

[2, 4, 2, 2, 2, 4, 2, 6]

출력

{8, 12, 6}

복잡도 분석

약수 탐색은 O(√S), 각 약수에 대한 검증은 O(S/약수)이므로 전체 시간 복잡도는 대략 O(S log S) 수준이며, 누적합 배열과 맵에 O(n)의 공간이 사용됩니다. 완전 탐색으로 모든 분할 지점을 조사하는 것보다 훨씬 효율적인 접근 방식입니다.