[백준 Java] 2143번 두 배열의 합

💡문제

[Gold III] 두 배열의 합 - 2143

문제 링크

성능 요약

메모리: 112696 KB, 시간: 556 ms

깨진 부분은 여기에서 확인

---

🤔접근법

범위 체크 및 시간복잡도 예상

• -1,000,000,000 ≤ T ≤ 1,000,000,000 (십억)
• 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000
• 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수
• $O(\sqrt T)$ 또는 $O(n^2)$이하 이어야 한다.

풀이법

❌ 접근 방법. 완탐

1. 배열 A의 가능한 부분 배열 만들기 → $O(N^2)$
2. 배열 B의 부분합이 T-(배열 A의 부분합)인 모든 부 배열 찾기 → $O(N^2)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^4)$

당연히 시간복잡도 초과

⭕ 접근 방법. Map을 이용해 누적합 저장하여 빠르게 조회

👇 Map을 이용해 배열의 누적합을 빠르게 조회하는 것은 아래 문제를 리뷰하며 자세히 기록해 두었다.
2015번 수들의 합 4

Map에 저장 해야 할 것은 key : 부분합으로 나올 수 있는 값 , value : 부분합을 key로 가지는 부분배열의 개수

Map을 통해 저장하면 누적합으로 같은 값을 가지는 배열의 개수를 알아낼 수 있다.

1. 배열 A와 배열 B에서 만들 수 있는 부분합 모두 구하기 → $O(N^3)$
   1-1. 1 ~ n까지 순회하며 배열의 누적합($S_n$)을 구한다. → $O(N)$
   1-2. 배열에서 $S_j$(j번째의 누적합)을 구하고 있다면 i ≤ j 조건을 만족하는 $S_j - Si$ 부분합을 모두 구한다. → $O(N^2)$
   1-3. 부분합을 key로 가지는 map이 존재하면 value에 +1, 존재하지 않는다면 map에 추가
2. 배열 A의 map의 key를 순회하며 T - (배열A의 부분합) 값을 배열 B의 map에 key로 존재하는지 확인
   → $O(N^2)$ 최대 부분합의 개수는 N*N이기 때문에 key를 순회하는게 N*N이다.
   2-1. 존재한다면 배열 A의 map의 value * 배열 B의 map의 value

➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$
스터디 →1000^3 는 십억인데 어떻게 통과하는지 이야기해보기.

---

😎SUCCESS

---

👩‍💻 코드

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

public class Main_2143 {
    static long T;  // 목표 합
    static int n;   // 배열 A의 크기
    static int m;   // 배열 B의 크기
    static long sumA[]; // 배열 A의 누적합
    static long sumB[]; // 배열 B의 누적합
    static HashMap<Long, Long> mapA; // 배열 A의 부분합과 그 등장 횟수를 저장하는 맵
    static HashMap<Long, Long> mapB; // 배열 B의 부분합과 그 등장 횟수를 저장하는 맵
    static long cnt; // 결과로 출력할 쌍의 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Long.parseLong(br.readLine());

        n = Integer.parseInt(br.readLine());

        // 배열 A에서 누적합 구하면서 가능한 부분합의 개수 구하기
        sumA = new long[n + 1];
        mapA = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= n; j++) {
            sumA[j] = sumA[j - 1] + Long.parseLong(st.nextToken());

            for (int i = 0; i < j; i++) {
                // 배열 A에서 i~j의 부분합을 키로 가지는 맵이 있다면 그 값을 반환해서 +1하고
                // 없다면 0(default)를 반환해서 +1 해라.
                mapA.put(sumA[j] - sumA[i], mapA.getOrDefault(sumA[j] - sumA[i], 0L) + 1);
            }
        }

        // 배열 B에서 누적합 구하면서 가능한 부분합의 개수 구하기
        m = Integer.parseInt(br.readLine());
        sumB = new long[m + 1];
        mapB = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= m; j++) {
            sumB[j] = sumB[j - 1] + Long.parseLong(st.nextToken());

            for (int i = 0; i < j; i++) {
                // 배열 B에서 i~j의 부분합을 키로 가지는 맵이 있다면 그 값을 반환해서 +1하고
                // 없다면 0(default)를 반환해서 +1 해라.
                mapB.put(sumB[j] - sumB[i], mapB.getOrDefault(sumB[j] - sumB[i], 0L) + 1);
            }
        }

        // mapA의 키 순회
        for (long key : mapA.keySet()) {
            // mapB에 T - (map의 key(부분합))을 key로 가진다면
            if (mapB.containsKey(T - key)) {
                // 해당 부분합이 몇 번 등장하는지를 계산하고 cnt에 더해준다.
                cnt += mapA.get(key) * mapB.get(T - key);
            }
        }

        // 결과 출력
        System.out.println(cnt);
    }
}