[백준][누적합-1] 2015번 수들의 합 4 자바 풀이

코테에서 틀린 문제만 팬다

1. 누적합
2. 트리
3. 조합

문제

A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.

N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는 정수의 절댓값은 10,000을 넘지 않는다.

출력

첫째 줄에 합이 K인 부분합의 개수를 출력한다.

예제 입력 1

4 0
2 -2 2 -2

예제 출력 1

4

예제 입력 2

6 5
1 2 3 4 5 0

예제 출력 2

3

풀이

1. 누적합을 통해 구간 합이 K인 구간의 갯수를 구한다.
2. 먼저 누적합 계산을 통해 0부터 N번 인덱스까지의 구간 합 계산
3. 매번 누적합 값 검사하면서, 현재 누적합 값을 Map에 추가
4. 이 후, 구간합 배열[i] - K의 값이 예전에 등장 했었다면, answer 값 증가

N - 8, K = 9 인 경우
인덱스:   0   1   2   3   4   5   6   7   8
배열:    [3] [4] [2] [5] [2] [3] [4] [5]
누적합:   0 → 3 → 7 → 9 → 14 → 16 → 19 → 23 → 28

		누적합[3] : 9 - K = 0 map에 0이라는 값이 있었음
		누적합[5] : 16 - 9 = 7 map에 7이라는 값이 있었음
		누적합[7] : 23 - 9 = 14 map에 14라는 값이 있었음
		누적합[8] : 28 - 9 = 19 map에 19라는 값이 있었음

코드

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

public class B2015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        long answer = 0;
        for (int j = 1; j <= N; j++) {
            answer += map.getOrDefault(sum[j] - K, 0);
            map.put(sum[j], map.getOrDefault(sum[j], 0) + 1);
        }

        System.out.println(answer);
    }
}