백준 2015 [자바] java 수들의 합4

문제 링크: https://www.acmicpc.net/problem/2015

2015번: 수들의 합 4

 

▶문제

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인 부분합의 개수를 출력한다.

▶해설

첫 번째로 풀었을 때는 dp를 이용하기 위해 List[] 배열을 이용해서 윗 값에서 추출하는 식으로 풀었습니다.

1<=N<=200,000 값이 크므로 메모리 초과가 떴습니다. 그래서 Map을 이용했습니다.

 

arr = 배열

sum = 배열을 차례대로 더한 값

 

ex)

arr = {2,-2,2,-2}

sum = {2,0,2,0}

 

이때 sum[i]-k ==0 일 때를 구해줍니다.

map.put(0,1) -> 합==k일 경우를 생각하여 1을 넣어줍니다.

count+=map.getOrDefault(sum[i]-k, 0) -> key값에 해당하는 값이 있다면 해당 값을 반환하며, 없다면 0을 반환합니다. 만약 sum[i]-k==0이라면 기존에 넣었던 1이 반환되며, count가 증가됩니다.

map.put(sum[i], map.getOrDefault(sum[i],0)+1) -> sum[i]의 해당하는 key값이 있었다면 해당 값 +1 을 해주며, 없었다면 0+1을 하여 sum[i]의 갯수의 합을 올려줍니다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;



public class Main {

    static int n,k;
    static int [] arr;
    static int [] sum;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        arr = new int[n+1];
        sum = new int[n+1];
        String[] s1 = br.readLine().split(" ");

        for(int i=1; i<=n; i++){
            arr[i]=Integer.parseInt(s1[i-1]);
            sum[i]=sum[i-1]+arr[i];
        }

        solve();
        System.out.println(count);
    }

    public static void solve() {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);

        for(int i=1; i<=n; i++){
            count+=map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i],map.getOrDefault(sum[i],0)+1);
        }
    }
}