Python에서 m으로 나눈 부분 배열 합의 최댓값 구하는 프로그램

문제 개요

n개의 원소를 가진 배열 nums와 정수 m이 주어졌을 때, 임의의 부분 배열(연속된 구간) 합을 m으로 나눈 나머지(modulo) 값 중 최댓값을 구하는 프로그램을 만들어 보겠습니다.

예를 들어 nums = [1, 5, 7, 3], m = 5가 입력으로 주어지면 정답은 3입니다. 모든 부분 배열의 합을 5로 나눈 결과는 다음과 같습니다.

[1] mod 5 = 1
[5] mod 5 = 0
[7] mod 5 = 2
[3] mod 5 = 3
[1, 5] mod 5 = 1
[5, 7] mod 5 = 2
[7, 3] mod 5 = 0
[1, 5, 7] mod 5 = 3
[5, 7, 3] mod 5 = 0
[1, 5, 7, 3] mod 5 = 1

나머지 값들 중 가장 큰 값은 3이므로 정답은 3이 됩니다.

알고리즘 접근 방법

모든 부분 배열을 일일이 확인하는 완전 탐색은 O(n²)의 시간이 걸립니다. 하지만 누적 합(prefix sum)과 이진 탐색(binary search)을 함께 활용하면 O(n log n)으로 효율적으로 해결할 수 있습니다.

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

누적 합을 미리 계산해 두면 임의의 구간 합은 두 누적 합의 차이로 구할 수 있습니다.
각 누적 합 s에 대해, 지금까지 등장한 누적 합 중 s보다 큰 값 중 가장 작은 값을 찾으면 (s − 그 값) mod m이 모듈로의 순환 특성 덕분에 매우 큰 값이 될 수 있습니다.
정렬된 상태를 유지하는 리스트에 bisect 모듈로 삽입 위치를 찾으면 이진 탐색 효과를 얻을 수 있습니다.

단계별 풀이 과정

csum: 첫 번째 원소를 nums[0] % m으로 초기화한 누적 합 리스트를 만듭니다.
두 번째 원소부터 각 x에 대해 (csum의 마지막 값 + x) % m을 csum 끝에 추가합니다.
seen := [0]으로 초기화합니다. (시작 인덱스 0에서 시작하는 부분 배열을 고려하기 위함)
max_sum := -1로 초기화합니다.
csum의 각 값 s에 대해 다음을 수행합니다.
- s를 seen에 정렬 순서를 유지하며 삽입할 가장 왼쪽 위치 idx를 찾습니다(bisect_left).
- idx가 seen의 크기보다 작으면 s보다 큰 값이 존재한다는 뜻이므로, max_sum을 max(max_sum, s, (s − seen[idx]) % m)으로 갱신합니다.
- 그렇지 않으면 max_sum을 max(max_sum, s)로 갱신합니다.
- s를 seen의 정렬된 올바른 위치에 삽입합니다.
max_sum을 반환합니다.

Python 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

import bisect

def solve(nums, m):
    csum = [nums[0] % m]
    for x in nums[1:]:
        csum.append((csum[-1] + x) % m)

    seen = [0]
    max_sum = -1
    for s in csum:
        idx = bisect.bisect_left(seen, s)
        if idx < len(seen):
            max_sum = max(max_sum, s, (s - seen[idx]) % m)
        else:
            max_sum = max(max_sum, s)
        bisect.insort_left(seen, s)

    return max_sum

nums = [1, 5, 7, 3]
m = 5
print(solve(nums, m))

입력

nums = [1, 5, 7, 3], m = 5

출력

복잡도 분석

시간 복잡도: O(n log n) — 각 누적 합에 대해 이진 탐색과 정렬된 삽입이 로그 시간에 처리됩니다.
공간 복잡도: O(n) — 누적 합 리스트와 seen 리스트를 저장해야 합니다.