[백준 2015번] 수들의합4

https://www.acmicpc.net/problem/2015

 

문제유형

• 누적합
• HashMap

 

문제 난이도

• Gold4

 

문제 분석

해당 문제는 N개의 정수가 저장되어 있는 배열이 있을 때, 부분합 중 합이 K인 것이 몇 개인지 출력하는 문제이다.

완전 탐색 O(N^2) -> 시간초과
이유: 1 <= N <= 200,000 이므로 단순하게 완전탐색을 진행할 경우, 시간초과가 난다.

나의 생각
내가 처음 문제를 보고 lowerBound, upperBound를 사용해서 해당 값의 차이가 K인 것의 개수를 찾아야겠다라고는 생각했지만, 그것의 개수를 어떻게 찾을지까진 생각하지 못해 다른 사람들의 풀이를 참고하였다.

문제 풀이
1 <= i <= j <= N, 누적합 배열 : sum 라고 정의
sum[j] - sum[i] = K 인 것을 생각하여, sum[i] = sum[j] - K
sum[j] - K와 값이 동일한 누적합의 개수를 추가해준다.
j > i 이므로 현재 가리키고 있는 j 이전에 누적합 중에 해당하는 값의 개수를 조회한다.

map.put(0, 1) 추가 이유 -> 만약, sum[i] = 0일 경우, 즉 처음부터 j까지 모두 더합 누적합이 K인 경우가 있을 수 있기 때문에 그럴 경우, 경우의 수 1개를 추가해줘야 하기 때문이다.
만약, 값을 넣어주지 않으려면 반복문에서 if(sum[j] == K) ans++; 를 작성해줘도 무방하다.

 

전체 코드

package _250701;

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

/**
 *packageName    : _250701
 * fileName       : BOJ_G4_2015_수들의합4
 * author         : moongi
 * date           : 7/1/25
 * description    :
 */
public class BOJ_G4_2015_수들의합4 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		long[] sum = new long[N + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i < N + 1; i++) {
			sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
		}

		HashMap<Long, Long> map = new HashMap<>();
		long ans = 0;

		map.put(0L, 1L);
		for (int i = 1; i < N + 1; i++) {
			ans += map.getOrDefault(sum[i] - K, 0L);
			map.put(sum[i], map.getOrDefault(sum[i], 0L) + 1);
		}

		sb.append(ans);
		System.out.println(sb);

	}
}