백준 2015번 문제풀이 이슈

[Rain3321]

algorithm_study/minwoo.lee_java/src/BOJ2015.java

Lines 20 to 31 in f9bedaf

	int[] prefixSum = new int[n + 1];
	prefixSum[0] = 0;
	for (int i = 1; i <= n; i++) {
	prefixSum[i] = prefixSum[i - 1] + nums[i];
	}
	numSums.put(0, 1);
	for (int i = 1; i <= n; i++) {
	result += (long) numSums.getOrDefault(prefixSum[i] - k, 0);
	int temp = numSums.getOrDefault(prefixSum[i], 0) + 1;
	numSums.put(prefixSum[i], temp);
	}

26번 라인의
numSums.put(0, 1);
을 논리적으로 설명해주세요

[minwoo9629]

어떠한 배열이 있을 때 그 배열의 부분합이 K를 만족하는 개수를 구하는 문제입니다.
부분합이 K를 만족하는 개수를 뜻하는 변수를 cnt라고 하겠습니다.

문제에서 주어진 배열 [2, -2, 2, -2]에 대한 누적 값은 [2, 0, 2, 0] 입니다.
누적합은 배열의 부분합입니다. 따라서 누적합이 K가 되면 cnt를 1 증가 시켜야합니다.

하지만 저의 코드는 누적 합을 구하면서 그 누적합이 문제에서 요구하는 K값이 됐을 때 카운트를 진행하지 않고
누적합이 K 값일 때의 카운트를 올리기 위해 numSums.put(0, 1);라는 코드로 표현하였습니다.
그렇다면 이 코드가 어떻게 논리적으로 맞는 코드인가에 대한 확인이 필요합니다.

배열 [N, 1, -N, 1]이고 K는 N일 때, 이에 대한 누적합이 [N, N+1, 1, 2]이가 됩니다.
그렇다면 우리는 prefixSum[i] - K(값으로는 0)를 만족하는 값이 HashMap있는지 확인을 해야합니다.
이를 값으로 보면 N-N 즉 0이라는 key 값이 HashMap numSusms에 있느냐 입니다.

numSums.put(0, 1);는 이 때 K의 값이 어떤 값이 든 prefixSum[i] - K각 index i에 해당하는 누적합 prefixSum[i] 가 K와 같을 때 카운트를 올리는 것과 같은 의미를 가지게 됩니다.

제 코드에 대하여 다시 한 번 생각해보고 위의 예시로 설명을 해보았습니다.

[Rain3321]

numSums.put(0, 1);는 이 때 K의 값이 어떤 값이 든 prefixSum[i] - K각 index i에 해당하는 누적합 prefixSum[i] 가 K와 같을 때 카운트를 올리는 것과 같은 의미를 가지게 됩니다.

이부분이 중요한 부분이군요. prefixSum[i] - K == 0 이라는 말은 prefixSum == K 와 같은 말이니까 같을 때의 카운트를 올린다...
그러면 같은 값이 나올때를 대비해 미리 1개를 올려두는거라 생각하는거죠?