[백준] 수들의 합4 (누적합)

문제 소개

백준 2015번 - 수들의 합4 문제를 정리합니다.

이 문제는 정수 배열 A에서 연속된 부분 구간의 합이 K인 경우의 개수를 구하는 문제입니다.
단, N(배열 길이)이 최대 200,000이므로 모든 구간을 직접 탐색하는 O(N²) 방식으로는 시간 내에 해결할 수 없습니다.

문제 링크: 수들의 합4 - 백준 2015번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 문제 입력 크기(N ≤ 200,000)를 보면 O(N²) 전수 탐색은 시간 초과가 된다.
2. 누적합(prefix sum) 을 사용하면 임의 구간 A[l..r]의 합을 O(1)로 구할 수 있다.
   sum(l..r) = prefix\[r\] - prefix\[l-1\].
3. prefix\[r\] - prefix\[l-1\] == K 이면 prefix\[l-1\] == prefix\[r\] - K 이므로,
   현재 인덱스 r에서 prefix[r] - K가 과거에 몇 번 등장했는지 세면 r로 끝나는 모든 합 K인 구간의 수를 알 수 있다.
4. 따라서 (누적합 값 → 등장 빈도) 를 저장하는 해시맵을 유지하면서 순회하면 전체 개수를 O(N)에 셀 수 있다.
   => Subarray Sum Equals K의 표준 기법

---

해결 과정 및 코드

핵심 아이디어

1. 누적합 빈도 맵 사용 (Map<누적합, 빈도>)
   • 현재 누적합 S에 대해 S - K가 과거에 f번 등장했다면, f만큼의 유효한 부분합(끝 인덱스가 현재)이 존재.
   • 매 인덱스마다 count += map[S - K], 그 후 map[S]++ 를 수행.
2. 초기값 map.put(0,1)의 의미
   • 구간이 배열의 첫 요소부터 시작하여 prefix[r] == K 인 경우를 세려면, prefix 가 이전에 0으로 한 번 등장했다고 가정.
   • 따라서 초기값으로 0의 빈도를 1로 설정.
3. 자료값 선택
   • count (정답)은 가능한 부분합의 최대 개수인 N*(N+1)/2 까지 커질 수 있음.
     예: N = 200,000일 때 최대 = 200000 * 200001 / 2 = 20,000,100,000 ≈ 2e10 → **32-bit int 범위(≈2.1e9)**를 넘습니다. 따라서 count는 반드시 long(64-bit)을 써야 합니다.
   • 값 (Map의 Value) : 해당 누적합이 지금까지 몇 번 등장했는지(빈도) 를 저장. 빈도는 최대 N(≈200k)이므로 int로 충분

코드

시간 복잡도 : O(N)

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		int N = read(), K = read();
		int[] a = new int[N];
		for (int i = 0; i < N; i++) a[i] = read();

		long count = 0;              // 합이 K인 부분합의 개수
		int prefixSum = 0;          // 0 ~ i까지의 누적합
		Map<Integer, Integer> map = new HashMap<>();

		// 누적합이 정확히 K인 구간 [0..i]을 포함하기 위해 0을 1개 넣어둠
		map.put(0, 1);

		for (int i = 0; i < N; i++) {
			prefixSum += a[i];

			/*
			 * 누적합의 차를 이용해 구간합을 계산하는 핵심 아이디어:
			 *
			 *   A[i] + A[i+1] + ... + A[j] = prefixSum[j] - prefixSum[i-1]
			 * → 따라서 prefixSum[j] - prefixSum[i-1] == K 이면, 해당 구간의 합이 K
			 * → 즉, prefixSum[i] - K가 과거에 몇 번 등장했는지를 세면,
			 *    그만큼의 구간(i보다 이전 j ~ i)에서 합이 K였다는 뜻이 됨
			 */
			count += map.getOrDefault(prefixSum - K, 0);

			// 현재 prefixSum 값을 map에 추가 (등장 횟수 누적)
			map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
		}

		System.out.println(count);
	}

	// 빠른 입력을 위한 read 함수
	public static int read() throws IOException {
		int cur, n = System.in.read() & 15;
		boolean isNegative = (n == 13);
		if (isNegative) n = System.in.read() & 15;
		while ((cur = System.in.read()) > 32) {
			n = (n << 3) + (n << 1) + (cur & 15);
		}
		return isNegative ? -n : n;
	}
}