[JAVA/투포인터] 백준 2143 두 배열의 합

1. 문제

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

2143번: 두 배열의 합

 

2. 풀이

투포인터를 사용해 풀이한다.

A의 부분합과 B의 부분합의 합을 구해야하는 상황이므로

1. A의 부분합과 B의 부분합을 미리 구해놓고
2. A의 부분합과 B의 부분합을 각각 정렬해
3. 투포인터를 이용해 합이 T일 경우, answer에 추가한다

    +) A의 부분합과 B의 부분합이 중복될 경우 한번에 처리해주기 위해, 합이 T일때 동일한 A의 부분합 갯수와 동일한 B의 부분합 개수를 따로 구하고 이를 곱해 answer에 더해준다.

 

3. 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

// 투포인터

public class Main_2143 {
    
    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[] arrA = new int[n];
        String[] ss= br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            arrA[i] = Integer.parseInt(ss[i]);
        }
        
        int m = Integer.parseInt(br.readLine());
        int[] arrB = new int[m];
        ss = br.readLine().split(" ");
        for(int i = 0; i < m; i++){
            arrB[i] = Integer.parseInt(ss[i]);
        }
        
        // A의 부분합 배열 
        ArrayList<Integer> sumA = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int sum = 0;
            for(int j = i; j < n; j++) {
                sum += arrA[j];
                sumA.add(sum);
            }
        }

        // B의 부분합 배열 
        ArrayList<Integer> sumB = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            int sum = 0;
            for(int j = i; j < m; j++) {
                sum += arrB[j];
                sumB.add(sum);
            }
        }
        
        Collections.sort(sumA);
        Collections.sort(sumB);
        
        // 투포인터
        long answer = 0, sum = 0;
        int aSize = sumA.size();
        int aIdx = 0, bIdx = sumB.size() - 1;
        while(aIdx < aSize && bIdx >= 0) {
            
            sum = sumA.get(aIdx) + sumB.get(bIdx);
            if(sum == T) { // 합이 T면
                
                // 겹치는 A의 부분합 개수 구하고 ... (1)
                int nowA = sumA.get(aIdx);
                int aDupCnt = 0;
                while(aIdx < aSize && sumA.get(aIdx) == nowA) {
                    aIdx++;
                    aDupCnt++;
                }
                
                // 겹치는 B의 부분합 개수를 구해 .... (2)
                int nowB = sumB.get(bIdx);
                int bDupCnt = 0;
                while(bIdx >= 0 && sumB.get(bIdx) == nowB) {
                    bIdx--;
                    bDupCnt++;
                }
                
                // (1)과 (2)를 곱한 값을 answer에 더함
                answer += (long)aDupCnt * (long)bDupCnt;
                
            }else if(sum < T) {
                aIdx++;
            }else {
                bIdx--;
            }
        }
        
        System.out.println(answer);
    }
}