자바 - 백준 2015 / 수들의 합 4

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

골드4

 

구현 방법

틀린 접근법

1. 모든 누적합을 구해, 원하는 값이 나오면 카운트 => 시간 초과

시간 복잡도가 O(n^2)이 되기 때문입니다.

 

올바른 접근법

sum(i) - sum(j - 1) = sum[j ... i]특징을 이용해야 합니다.

현재 저희는 목표값 K를 구해야 하기 때문에 sum[i] - sum[j - 1] = K인 값을 구하는게 목표입니다.

이 식은 sum[i] - K = sum[j - 1]로 바꿀 수 있습니다.

이를 통해 현재까지의 부분합에서 목표값 K를 뺏을 때의 값이 존재하는지 확인하면서 갱신해주는 방법으로 구현하면 O(n)으로 답을 낼 수 있습니다.

코드

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

/**
* 백준 2015
* 수들의 합 4
* 골드4
* https://www.acmicpc.net/problem/2015
*/
public class Boj2015 {

    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());

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

        Map<Long, Long> m = new HashMap<>();
        long count = 0;

        m.put(0L, 1L);
        for(int i = 1; i <= N; i++) {
            count += m.getOrDefault(sum[i] - K, 0L);

            m.put(sum[i], m.getOrDefault(sum[i], 0L) + 1);
        }

        System.out.println(count);

    }
}