Q 2143 두 배열의 합

💡 문제 요약 및 분석

배열 A, B가 주어질 때 각 배열의 부분 배열의 합이 T 인 경우의 수를 전부 찾아라.

💡 알고리즘 설계

✅ 배열 B 의 부분합 결과를 Map 에 저장하는 것이 킥이다.

1. 입력

   • 표준입력을 받아 int T 생성
   • 표준입력을 받아 누적합 배열 int[N+1] A, int[M+1] B 생성

2. 연산

   • 다음과 같은 공식을 생각할 수 있다. T = A(i,j) + B(k,l) ➡️ T - A(i,j) = B(k,l)
   • 배열 B 를 이중 for 문으로 돌리면서 모든 부분합의 결과를 key 로, value 는 중복을 체크하기 위해 기존 value++ 로 저장한다. (최대 1,000,000 반복)
   • 배열 A 를 이중 for 문으로 돌리면서 T - A(i,j) 를 계산한 결과가 Map 에 있는지 찾고, 해당 value 값을 count++ 한다. (최대 1,000,000 반복)

3. 출력

   • count 변수를 출력한다.

💡 코드

import java.io.*;
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));
        int T = Integer.parseInt(br.readLine());

        // 누적합 배열 A 생성
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < A.length; i++) {
            A[i] = A[i - 1] + Integer.parseInt(st.nextToken());
        }

        // 누적합 배열 B 생성
        int M = Integer.parseInt(br.readLine());
        int[] B = new int[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < B.length; i++) {
            B[i] = B[i - 1] + Integer.parseInt(st.nextToken());
        }

        // 누적합 배열 B 의 부분합을 전부 저장
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < B.length - 1; i++) {
            for (int j = i + 1; j < B.length; j++) {
                int key = B[j] - B[i];
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        // T - A(i,j) 연산 개시
        long count = 0;
        for (int i = 0; i < A.length - 1; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int cal = T - (A[j] - A[i]);
                count += map.getOrDefault(cal, 0);
            }
        }

        System.out.println(count);
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n^2 + m^2)	O(m^2)