백준 2143 JAVA : 두 배열의 합

문제

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

2143번: 두 배열의 합

 

풀이 예상

이 전에 바로 누적 합 문제를 풀었었기 때문에 바로 누적합이 떠올랐다.

 

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

백준 2015(수들의 합4)풀이  풀이 방법 은 비슷하게 풀어서 상세하게는 설명하지 않고 달랐던 부분만 적어보겠다.

A 배열에서 부 배열의 합을 Amap에 저장한다. (key: 합, value: 개수)

마찬가지로 B배열에서 부 배열의 합을 Bmap에 저장한다.

 

Amap을 전부 순회하면서 Bmap에 (T - A의 키값)을 만족하는 값이 있다면 그 value 와 A의 value값을 곱한 수를 answer에 더한다.

 

=> 시간복잡도 .. O(n^2) 까진 알겠는데 해시 맵을 순회하는 부분의 시간복잡도를 잘 모르겠다ㅠ

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

public class Main {
    static long answer;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        HashMap<Integer, Long> Amap = new HashMap<>();
        HashMap<Integer, Long> Bmap = new HashMap<>();

        int[] sumA = new int[n+1]; // sum[i] = 1~i까지의 합
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                int key = sumA[i] - sumA[i - j];

                if (Amap.containsKey(key)) {
                    Amap.put(key, Amap.get(key) + 1);
                } else {
                    Amap.put(key, 1L);
                }

            }

        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] sumB = new int[m+1]; // sum[i] = 1~i까지의 합

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= i; j++) {
                int key = sumB[i] - sumB[i - j];

                if (Bmap.containsKey(key)) {
                    Bmap.put(key, Bmap.get(key) + 1);
                } else {
                    Bmap.put(key, 1L);
                }

            }

        }

        Amap.forEach((key,value) -> {
            int needKey = T - key;
            if(Bmap.containsKey(needKey)) {
                answer += (value* Bmap.get(needKey));
            }
        });

        System.out.println(answer);

    }
}

결과