[백준] 2015: 수들의 합 4 - JAVA

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

 

풀이

주어진 수열에서 부분 수열의 합이 k가 되는 경우를 찾는 문제이다.

 

누적합과 맵을 이용해 해결했다.

 

```sum[i]```에서 k를 뺀 값이 이전에 등장한 적이 있는지를 확인한다.

 

현재 누적합이 ```sum[i]```라고 할 때, ```sum[i]-k```가 이전에 등장한 적 있다면 그 구간의 합이 k라는 것을 의미한다.

 

---

 

메모리: 33452KB
시간: 348ms
언어: Java 11

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

public class Main {
    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());

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

        long answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 1; i < n + 1; i++) {
            answer += map.getOrDefault(sum[i] - k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }

        System.out.println(answer);
    }

}