문제 설명
배열 nums와 정수 p가 주어졌을 때, 남은 값들의 합이 p로 나누어떨어지도록 가장 짧은 부분 배열(단, 전체 배열은 제외)을 제거해야 합니다. 우리가 구해야 할 것은 제거해야 하는 부분 배열의 최소 길이이며, 조건을 만족하는 부분 배열이 존재하지 않는다면 -1을 반환합니다.
예를 들어 입력이 nums = [8,2,6,5,3], p = 7이라면 출력은 1이 됩니다. 값 3을 제거하면 전체 합이 24 - 3 = 21이 되고, 21은 7로 나누어떨어지기 때문입니다.
해결 접근 방법
이 문제는 누적 합(prefix sum)과 모듈로 연산, 그리고 해시 맵을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 전체 합을 p로 나눈 나머지를 s라고 할 때, 제거할 부분 배열의 합을 p로 나눈 나머지 역시 s가 되어야 합니다.
- 누적 합의 나머지 값을 인덱스와 함께 저장하면, 두 지점 사이의 부분 배열 합의 나머지를 빠르게 계산할 수 있습니다.
구체적인 단계는 다음과 같습니다.
- 정답 변수 ans를 무한대(infinity)로 초기화합니다.
- s := nums의 모든 원소 합을 p로 나눈 나머지로 설정합니다.
- 맵 d를 {0: -1} 키-값 쌍으로 초기화합니다.
- 누적 합 변수 cum을 0으로 초기화합니다.
- s가 0이면 이미 전체 합이 p로 나누어떨어지므로 0을 반환합니다.
- i를 0부터 nums의 크기까지 반복하며 다음을 수행합니다.
- cum := cum + nums[i]
- r := cum mod p
- (r - s) mod p가 d에 존재하면, ans := min(ans, i - d[(r-s) mod p])로 갱신합니다.
- d[r] := i로 저장합니다.
- ans가 nums의 크기보다 작으면 ans를, 그렇지 않으면 -1을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums, p):
ans = float("inf")
s = sum(nums) % p
d = {0:-1}
cum = 0
if s == 0:
return 0
for i in range(len(nums)):
cum += nums[i]
r = cum % p
if (r-s) % p in d:
ans = min(ans, i-d[(r-s)%p])
d[r] = i
return ans if ans < len(nums) else -1
nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))입력
[8,2,6,5,3], 7
출력
1
마무리
이 알고리즘은 각 원소를 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 해시 맵에 최대 n개의 나머지 값을 저장하므로 공간 복잡도 역시 O(n)입니다. 누적 합과 모듈로 연산의 성질을 결합하면 브루트 포스 방식(O(n²))보다 훨씬 효율적으로 문제를 해결할 수 있습니다.