[ BOJ ][JAVA][2143] 두 배열의 합

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	64 MB	10050	3045	1977	28.557%

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

예제 입력 1

5
4
1 3 1 2
3
1 3 2

예제 출력 1

7

코드

슬라이딩 윈도우 풀이

/*
단순 부분합이 아니라, 연속된 부분합이라면 투포인터를 사용한다음에 또다시 투포인터를 활용한다
*/
import java.io.*;
import java.util.*;

public class p2143 {
    static int t, n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // target number
        t = Integer.parseInt(br.readLine());

        n = Integer.parseInt(br.readLine());
        int arr1[] = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine());
        int arr2[] = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        tp(arr1, list1);
        tp(arr2, list2);

        Collections.sort(list1);
        Collections.sort(list2);

        int left = 0;
        int right = list2.size() - 1;
        long result = 0;
        while (left < list1.size() && right >= 0) {
            int left_value = list1.get(left);
            int right_value = list2.get(right);

            if (left_value + right_value == t) {
                long left_cnt = 0;
                long right_cnt = 0;

                while(left < list1.size() && left_value == list1.get(left)) {
                    left++;
                    left_cnt++;
                }

                while(right >= 0 && right_value == list2.get(right)) {
                    right--;
                    right_cnt++;
                }
                result += left_cnt * right_cnt;
            } else if (left_value + right_value > t) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(result);
    }

    static void tp(int[] arr, List<Integer> list) {
        int lo = 0, hi = 0, sum = 0;
        while (lo < arr.length) {
            sum += arr[hi++];

            list.add(sum);
            if (hi == arr.length) {
                lo++;
                hi = lo;
                sum = 0;
            }
        }
    }
}

HashMap 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
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());
        int n = Integer.parseInt(br.readLine());        
        int[] a = new int[n];
        String[] temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(temp[i]);
        int m = Integer.parseInt(br.readLine());
        int[] b = new int[m];
        temp = br.readLine().split(" ");
        for (int i = 0; i < m; i++)
            b[i] = Integer.parseInt(temp[i]);
        int[] sumA = new int[n * (n + 1) / 2];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                sumA[idx++] = sum;
            }
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = i; j < m; j++) {
                sum += b[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        long ans = 0;
        for (int sum : sumA)
            ans += map.getOrDefault(t - sum, 0);
        System.out.println(ans);
    }
}