[JAVA] 백준 2015 누적 합

 

 

2015번: 수들의 합 4

문제

구간 합들 중에서 K가 되는 구간의 경우의 수를 구하시오.

풀이

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

public class Main {
    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())+1;
        int K = Integer.parseInt(st.nextToken());

        int[] A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<N; i++){
            A[i] = A[i-1] + Integer.parseInt(st.nextToken());
        }

        int count = 0;
        int start = 0;
        int end = 1;
        while(start < N-1){
            if(A[end++] - A[start] == K) count++;
            if(end == N) {
                start++;
                end = start+1;
            }
        }

        System.out.println(count);
    }
}

시간이 자꾸 초과해서 풀지 못했다 어떻게 해결해야하는걸까?

다음과 같이 해결했다.

누적합만으로는 해결이안되서 인터넷 서칭을 통해서 풀이를 이해해보았다.

이중 for문과 투포인터를 사용해서는 문제 해결이 안되었고 찾아본 결과 좀 독특한 방법으로 해결하는 방식이 있었다.

첫 번째, 먼저 누적합을 구하면서 누적합이 K인 값을 알아내어 카운트한다.

두 번째, 다시 누적합을 N번 돌면서 만약 누적합[i] - K인 key를 가진 값이 있는지 탐색한다. 만약 있다면 count에 더해준다.

세 번째, 현재 누적합을 Map에 담아준다.

요점은 누적합[i]-K가 되는 key를 찾아서 더해주는 것인데

현재 누적합[i] - (누적합[i] - K) = K가 나오기 때문이다. 이를 통해서 모든 누적합들을 돌아가면서 연산하지 않고도 해결이 가능했다.!

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

public class Main {
    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())+1;
        int K = Integer.parseInt(st.nextToken());

        int[] A = new int[N];
        long count = 0;
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<N; i++){
            A[i] = A[i-1] + Integer.parseInt(st.nextToken());
            if(A[i] == K) count++;
        }

        Map<Integer, Integer> value = new HashMap<>();
        for(int i=1; i<N; i++){
            if(value.containsKey(A[i]-K)){
                count += value.get(A[i]-K);
            }

            if(value.containsKey(A[i])) value.put(A[i], value.get(A[i]) + 1);
            else{
                value.put(A[i], 1);
            }
        }

        System.out.println(count);
    }
}

결과

 

더 열심히 해야겠다. 정말 어렵다.