백준 2015 JAVA : 수들의 합4

문제

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

2015번: 수들의 합 4

 

풀이 예상

N의 개수가 200,000 개 이기 때문에 부분 합 전체를 구해서 풀면 시간초과가 날 것 같았다.

문제에서 주어진 부분 합이란 배열 자리 수가 연속된 숫자이기 때문에 누적 합을 통해서 풀 수 있을 것 같다고 생각했다.

 

풀이방법 (접근 방법 & 시간복잡도)

누적합을 배열에 저장해 두고, 이 전에 나온 누적합과의 차이로 문제에서 요구하는 K 의 값을 만족하면 answer의 값을  증가한다.

 

문제 예시에 나온(N = 4, K = 0, [2, -2, 2, -2]) 를 예시로 들어보면, 누적 합 배열은 이렇게 저장된다.

sum[0]	sum[1]	sum[2]	sum[3]
2	0	2	0

 

해시맵 초기는 이렇게 설정한다.

HashMap key	0
value(개수)	1

 

여기서, 순서대로 sum[0] 부터 보면

sum[0] = 2이고, K = 0 이니까 sum[0] 을 0 (K의 값)으로 만드려면 2 라는 숫자가 필요하다.(sum[0] - K 의 값)

해당 숫자는 가지고 있지 않으니 정답 카운트는 늘지 않고, 해시 맵에 sum[0] 의 값을 추가한다.

HashMap key	0	2
value(개수)	1	1

 

sum[1]을 보면

sum[1] = 0, K= 0 이니까 sum[1] 을 0(K의 값)으로 만드려면 0 이 필요하다. (sum[1] - K 의 값)

해당 숫자는 해시맵에 가지고 있으니 0의 value인 1만큼 정답 카운트를 늘리고, 해시맵에 sum[1] 의 값을 추가한다.

=> 이 때, 이미 0이라는 key 값이 있으므로 value를 +1 해 준다. 

(answer = 1)

HashMap key	0	2
value(개수)	2	1

 

 

sum[2]을 보면

sum[2] = 2, K= 0 이니까 sum[2] 을 0(K의 값)으로 만드려면 2 라는 숫자가 필요하다. (sum[2] - K 의 값)

해당 숫자는 해시맵에 가지고 있으니 2의 value인 1만큼 정답 카운트를 늘리고, 해시맵에 sum[2] 의 값을 추가한다.

=> 이 때, 이미 2라는 key 값이 있으므로 value를 +1 해 준다. 

(answer = 2)

HashMap key	0	2
value(개수)	2	2

 

sum[3]을 보면

sum[3] = 0, K= 0 이니까 sum[3] 을 0(K의 값)으로 만드려면 0 이 필요하다. (sum[3] - K 의 값)

해당 숫자는 해시맵에 가지고 있으니 0의 value인 2만큼 정답 카운트를 늘린다.

(answer = 4)

 

 

 

1.  sum[] 배열에 누적 합을 저장한다. sum[i] 는 1~i까지의 합 이다.

2. 해시맵에 이전에 나왔던 누적합을 key로, 개수를 value로 저장한다. 이때, value는 int값을 넘을 수 있으므로 long으로 선언한다.

3. 해시맵에 key: 0, value: 1 을 추가한다.(후에 for문을 돌면서 자기자신 만으로 K를 만족하는 경우를 만들어주기 위해)

4. for문을 돌면서 필요한 키 값이 해시맵에 있으면 answer를 증가시킨다.

5. 해시맵에 지금의 누적합을 추가한다.

 

 => O(n) 의 시간 복잡도로 해결 가능하다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        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]; // sum[i] = 1~i까지의 합
        st = new StringTokenizer(br.readLine());

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

        long answer = 0;

        HashMap<Integer,Long> hm = new HashMap<>();
        hm.put(0,1L);

        for (int i = 1; i <= N; i++) {
            int findKeyNum = sum[i] - K;
            if(hm.containsKey(findKeyNum)) {
                answer += hm.get(findKeyNum);
            }

            if(hm.containsKey(sum[i])) {
                hm.put(sum[i], hm.get(sum[i])+1);
            }else {
                hm.put(sum[i], 1L);
            }

        }

        System.out.println(answer);

    }
}

 

결과