[백준/Gold IV] 수들의 합 4 - 2015

[Gold IV] 수들의 합 4 - 2015

문제 링크

성능 요약

메모리: 40288 KB, 시간: 420 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 누적 합, 트리를 사용한 집합과 맵

제출 일자

2024년 11월 14일 03:51:00

문제 설명

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

제출코드

//https://www.acmicpc.net/problem/2015
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));
        // n, k 입력 받기(n:정수 수, k:합)
        int[] nk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nk[0], k = nk[1];
 
        // 배열 입력 받기
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        long sum = 0 ; // 현재 위치까지의 합
        HashMap<Long, Integer> cnt = new HashMap<>(); // sum의 등장 횟수를 저장
        cnt.put(0L, 1); // 처음 sum은 0
        long answer = 0;
        for(int i = 0; i < n; i++) {
            sum += arr[i];
            // (sum - k)를 한 수가 한번 이상 등장했으면 해당 횟수만큼 answer에 추가.
            answer += cnt.getOrDefault(sum-k, 0);
            cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
        }
        System.out.println(answer);
    }
}