Python으로 배열을 합이 같은 K개의 연속 부분 배열로 분할 가능한지 확인하는 방법

숫자로 이루어진 배열 nums와 정수 K가 주어졌을 때, nums를 K개의 연속된(contiguous) 부분 배열로 나누면서 각 부분 배열의 원소 합이 모두 같아지도록 할 수 있는지 확인해야 합니다.

문제 이해하기

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

nums = [2, 5, 3, 4, 7], k = 3

이 경우 출력은 True가 됩니다. 배열을 아래와 같이 세 구간으로 나누면 각 부분의 합이 모두 7로 동일하기 때문입니다.

(2, 5), (3, 4), (7) → 각각의 합은 모두 7

해결 접근 방식

이 문제는 누적 합(prefix sum) 개념을 활용하면 효율적으로 해결할 수 있습니다. 전체 합이 K로 나누어떨어지지 않으면 바로 False를 반환하고, 그렇지 않다면 누적 합 배열을 순회하며 목표 합(total_sum / k)에 도달하는 지점을 세면 됩니다. 단계별 과정은 다음과 같습니다.

• n := nums의 길이
• cumul_sum := nums의 모든 원소에 대한 누적 합 배열
• total_sum := cumul_sum[n - 1], 즉 배열의 전체 합
• 만약 total_sum이 k로 나누어떨어지지 않으면
  • False 반환
• count := 0, pos := -1로 초기화
• i를 0부터 n-1까지 반복하면서
  • pos가 -1이면 sub := 0, 그렇지 않으면 sub := cumul_sum[pos]
• cumul_sum[i] - sub가 total_sum / k와 같으면
  • pos := i로 갱신하고 count를 1 증가
• 그렇지 않고 cumul_sum[i] - cumul_sum[pos]가 total_sum / k보다 크면
  • 반복문 탈출 (더 이상 분할 불가능)

마지막으로 count가 k와 같으면 True, 아니면 False를 반환합니다.

구현 예제

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

def solve(nums, k):
    n = len(nums)
    cumul_sum = [0 for i in range(n)]
    cumul_sum[0] = nums[0]
    for i in range(1, n):
        cumul_sum[i] = cumul_sum[i - 1] + nums[i]
    total_sum = cumul_sum[n - 1]
    if total_sum % k != 0:
        return False
    count = 0
    pos = -1
    for i in range(n):
        if pos == -1:
            sub = 0
        else:
            sub = cumul_sum[pos]
        if cumul_sum[i] - sub == total_sum / k:
            pos = i
            count += 1
        elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
            break
    return count == k

nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

입력

[2, 5, 3, 4, 7], 3

출력

True

시간 복잡도

누적 합 계산에 O(n), 배열 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n)입니다. 추가로 사용되는 누적 합 배열 때문에 공간 복잡도 역시 O(n)입니다.