[백준] 2015 수들의 합 4 - Java

 

 

 

이중 for문을 돌면 당연히 시간 초과가 난다 -_-

 

먼저 입력받은 수들에 대해 누적 합 배열을 만들고 시작한다.

해시 맵은 누적 합 배열을 돌면서 해당 값이 나온 횟수를 저장하고, 현재 값 - 목표 값을 확인해 답을 갱신할 때 사용한다.

 

일단 누적 합 배열을 만들어놓으면 sum_arr[6] - sum_arr[3] == arr[4] + arr[5] + arr[6] 이렇게 사용할 수 있으니..

 

누적 합 배열을 돌면서 배열의 값이 찾으려는 값과 같으면 ans 1 증가.

나머지는 위에서 설명한 대로.

 

 

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));        
        StringBuilder sb = new StringBuilder();      
        
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

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

        int[] arr = new int[N+1];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<N+1; i++){
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        HashMap<Integer, Integer> hm = new HashMap<>();

        long result = 0;
        long cnt = 0;

        for(int i=1; i<N+1; i++){
            if(arr[i] == K){
                result++;                
            }

            if(hm.containsKey(arr[i] - K)){
                cnt = hm.get(arr[i] - K);
            }else{
                cnt = 0;
            }
            
            result += cnt;
            
            if(hm.containsKey(arr[i])){
                hm.put(arr[i], hm.get(arr[i]) + 1);
            }else{
                hm.put(arr[i], 1);
            }
        }

        System.out.println(result);

        
    }
}