[백준/G4/투포인터/자바] 2143. 두 배열의 합

💡 문제

 

한 배열 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 ( -10억 <= T <= 10억 )

둘째줄 N ( 1 <= N <= 1000 )

셋째줄 배열N의 원소 ( 0 <= 원소 <= 100만 )

넷째줄 M  ( 1 <= M <= 1000 )

다섯째줄 배열M의 원소 ( 0 <= 원소 <= 100만 )

 

💻 출력 / 제한

 

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

 

---

 

풀이 방법

 

문제 유형 : 투 포인터 / 자료구조 ( 해쉬 맵 )

 

문제를 읽고 든 생각

: 일단 부배열 구현 하자!

 

 

 

→ 부배열로 T를 만들려는 경우의수는 A부배열 길이 * B 부배열 길이이다.

 

부배열의 최대길이는 ?

 

a배열의 길이는 최대 1000 / 부배열의 최대길이는 1001* 500 = 50만 이다.

50만 * 50만 = 2500억 이다.

 

찾는 방법 

 

1. 투포인터

2. 해시 맵

 

---

투포인터 풀이

 

구현 방법

 

sum = A[aPointer] + B[bPointer]

if ( T > sum ) bPointer++;

if( T < sum ) aPointer++;

 

T를 찾을 경우

 

 

 

중복 위치 체크

 

while( if( a[i] == a[i+1] ) ) aPointer++; aCount++;

while( if( b[i] == b[i+1] )) bPointer++; bCount++;

count += aCount * bCount;

aPointer / bPointer 경우의수는 모두 구했으므로 aPointer++; bPointer++;

 

※ 주의할점

aCount = 50만 / bCount = 50만 → 2500억

int count

long 자료형을 사용 해야 한다.

 

---

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class TwoArraySum2143 {
    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 = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int M = Integer.parseInt(br.readLine());
        int[] arrB = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();

        // arrA의 부배열
        for(int i = 0; i < N; i++){
            int count = 0;
            for(int j = i; j < N; j++){
                count += arrA[j];
                listA.add(count);
            }
        }

        // arrB의 부배열
        for(int i = 0; i < M; i++){
            int count = 0;
            for(int j = i; j < M; j++){
                count += arrB[j];
                listB.add(count);
            }
        }

        // listA 오름차순 정렬
        Collections.sort(listA);
        // listB 내림차순 정렬
        listB.sort(Comparator.reverseOrder());

        int aPointer = 0;
        int bPointer = 0;
        long count = 0;

        while (aPointer < listA.size() && bPointer < listB.size()) {
            int sum = listA.get(aPointer) + listB.get(bPointer);

            // pointer index 합이 T와 같을 경우
            if (sum == T) {
                long aCount = 1, bCount = 1;

                // listA 동일한 값을 가진 요소 개수
                while (aPointer + 1 < listA.size() && listA.get(aPointer).equals(listA.get(aPointer + 1))) {
                    aPointer++;
                    aCount++;
                }

                // listB 동일한 값을 가진 요소 개수
                while (bPointer + 1 < listB.size() && listB.get(bPointer).equals(listB.get(bPointer + 1))) {
                    bPointer++;
                    bCount++;
                }

                count += aCount * bCount;
                aPointer++; bPointer++;

            } else if (sum < T) aPointer++;
             else bPointer++;
        }
        System.out.println(count);
    }
}