문제 개요
음수가 아닌 정수로 구성된 리스트 nums와 양의 정수 k가 주어졌을 때, 길이가 2 이상이면서 원소들의 합이 k의 배수가 되는 연속된 부분 리스트(sublist)가 존재하는지 판별하는 프로그램을 작성해 보겠습니다.
예를 들어 입력이 nums = [12, 6, 3, 4], k = 5라면 결과는 True입니다. 부분 리스트 [12, 3]의 합이 15이고, 15는 5로 나누어 떨어지기 때문입니다.
접근 방법: 누적 합과 나머지 활용
모든 부분 리스트를 일일이 확인하는 완전 탐색은 O(n²) 이상의 시간이 걸립니다. 하지만 누적 합(prefix sum)을 k로 나눈 나머지를 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 두 지점까지의 누적 합을 k로 나눈 나머지가 서로 같다면, 그 사이 구간의 합은 반드시 k의 배수입니다.
- 따라서 각 나머지 값이 처음 등장한 인덱스를 딕셔너리에 저장해 두고, 같은 나머지가 다시 나타날 때 두 인덱스의 차이가 2 이상인지 확인하면 됩니다.
- 차이가 2 이상이어야 하는 이유는 부분 리스트의 길이가 최소 2여야 하기 때문입니다.
알고리즘 단계
- sum := 0 으로 초기화합니다.
- m := 빈 딕셔너리를 생성하고, m[0] := -1 로 설정합니다. (처음부터 시작하는 구간을 처리하기 위함입니다.)
- i를 0부터 리스트 끝까지 반복하며 다음을 수행합니다.
- sum := sum + nums[i]
- sum := sum mod k
- 만약 sum이 m에 이미 존재하고, i − m[sum] ≥ 2 라면 True를 반환합니다.
- 그렇지 않으면 m[sum] := i 로 저장합니다.
- 반복이 끝나면 조건을 만족하는 부분 리스트가 없으므로 False를 반환합니다.
구현 예제
class Solution:
def solve(self, nums, k):
total = 0
m = {}
m[0] = -1
for i in range(len(nums)):
total += nums[i]
total %= k
if total in m:
if i - m[total] >= 2:
return True
else:
m[total] = i
return False
ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))
입력
[12, 6, 3, 4], 5
출력
True
동작 과정 살펴보기
입력 [12, 6, 3, 4], k = 5의 경우 누적 합의 나머지는 다음과 같이 변합니다.
- i=0: 누적 합 12 → 나머지 2 → 딕셔너리에 {2: 0} 저장
- i=1: 누적 합 18 → 나머지 3 → 딕셔너리에 {3: 1} 저장
- i=2: 누적 합 21 → 나머지 1 → 딕셔너리에 {1: 2} 저장
- i=3: 누적 합 25 → 나머지 0 → 이미 m[0] = -1이 존재하고, 3 − (-1) = 4 ≥ 2 이므로 True 반환
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회합니다.
- 공간 복잡도: O(min(n, k)) — 나머지 값은 0부터 k−1까지만 존재하므로 딕셔너리 크기가 제한됩니다.