❤️[백준] 2143 두 배열의 합 java

1. 문제 설명 📌

문제 링크

두 배열의 구간합끼리 더해서 목표값인 T가 나오는 횟수를 세는 문제

2. 접근 방식 🗃️

KEY WORD: Two Pointer, Range sum

이번 문제는 각 배열에서 나올 수 있는 구간합을 모두 구해서 List 화 시킨 뒤에, 이 두 List에서 값을 각각 꺼내어 보며, T가 될 수 있는 경우의 수를 세야한다. 한마디로 요약하면 구간합 후보군들 사이에서 Two Pointer로 요약할 수 있다.

(1) 왜 그렇게 풀어야 하나요?

답: 배열의 원소로 음수가 존재

이 문제의 까다로운 점은 배열의 원소로 음수가 존재할 수 있다는 것이다. 누적합을 활용한 구간합을 구하는데 기본이 되는 전제 조건은 "right 포인터를 늘리면 구간합이 커진다. left 포인터를 늘리면 구간합이 줄어든다. " 인데,이번 문제에서는 음수가 누적될 경우, 이것이 전제되지 않기 때문에, 값을 예측할 수 없어 전수조사가 필요해진다.

예시를 들어보자. 위의 그림은 양수로 이루어진 배열과 그 누적합이다. value[B] - value[A] 구간의 합은 3이다. 구간합이 2인 경우를 찾는다고 쳤을 때, 우리는 A를 오른쪽으로 이동시켜서 구간 합을 줄이려 노력했을 것이다. 양수로 이루어진 배열의 구간합의 경우 이와 같이 행동에 기준을 세울 수 있다.

반면, 이번 그림의 경우, 음수가 섞여 있기 때문에 B를 오른쪽으로 이동 시킨다고 해서, 구간합이 증가함을 예측할 수 없다. 따라서 전수조사가 필요하게 된다.

' 이번 문제에서 전수조사 하면 되지 않나?'라고 생각할 수 있지만, 시간 복잡도를 예측해보면, 완전탐색으로 절대 풀 수 없다. 먼저 배열의 원소 수 최대값이 1000이고 누적합 배열도 같은 수를 가질 것이다. A배열을 기준으로 구간합을 구할 경우, 완전 탐색을 해야하므로 이중 반복문이 필요하다. A에서 구한 구간합으로 T가 가능한 B 구간합을 위해서 또 이중 반복문이 필요하다. 둘은 연속되므로, 최종적으로 4중 반복문이 필요하게 된다. 이건 (10^3)^4 = O(10^12)이므로, 1억 번의 연산을 훨씬 뛰어넘는다.

(2) 푸는 법 자세히 설명

• A 배열과 B 배열 모두 나올 수 있는 구간합을 모두 구해서 LIST에 저장
• LIST를 오름차순으로 정렬 (➜ 투 포인터 진행 시 값들을 예측할 수 있기 위함)
• 마주 보는 투 포인터 진행하여 T가 될 수 있는 값들을 체크
  (A 구간합 List에서는 왼쪽(오름차순) 출발, B 구간합 List에서는 오른쪽 (내림차순) 출발)
  • 중복되는 A,B 값들로 T가 완성될 수 있음. ➜ 내부 반복문으로 빠르게 처리

잠깐!✋마주보는 투포인터를 진행하는 이유?

답: 중복된 반복문을 피할 수 있다.

목표 값(T)를 8이라고 할 때, B가 10을 가르키는 경우, A = -2 이외에 해당 값을 완성 시킬 수 있는가? 없다. 왜냐하면 A는 앞으로 계속 커질 것이기 때문이다. 이때는 B를 움직여 값을 줄여야 한다. 반대로 A가 -2일때도 B = 10 이외의 다른 어떤 값도 T=8을 만족시킬 수 없다. 왜냐하면 앞으로 만날 값들은 B=10보다 작기 때문이다. 이렇게 마주보는 투 포인터를 사용하면, 행동에 따른 결과를 예측 할 수 있다.

3. 코드 소개 🔎

import java.io.*;
import java.util.*;

public class Main {

    /* b2143 두 배열의 합
    1. 각 배열의 구간합 구하기
    2. A 구간합을 기준으로 B 구간합을 더한다.
    3. B 구간합을 더했을 때, 총 계산 결과가 T를 넘어서면, A 구간합의 위치를 옮긴다.
    */

    public static void main(String[] args) throws IOException {
        // 0. 변수 모음
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        int [] A;
        int [] B;
        int [] sumA;
        int [] sumB;
        ArrayList<Integer> secA = new ArrayList<>();
        ArrayList<Integer> secB = new ArrayList<>();
        // 1. 초기화
        T = Integer.parseInt(br.readLine());
        A = new int [Integer.parseInt(br.readLine())+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < A.length; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        B = new int [Integer.parseInt(br.readLine())+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < B.length; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        sumA = new int [A.length];
        sumB = new int [B.length];
        initSums(sumA, A);
        initSums(sumB, B);
        initSec(secA,sumA);
        initSec(secB,sumB);
        Collections.sort(secA);
        Collections.sort(secB);


        // 2. 계산
        System.out.println(calcul(secA,secB,T));
    }
    // 누적합 초기화 함수
    public static void initSums (int [] sum, int [] arr){
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i-1] + arr[i];
        }
    }
    // 구간합 초기화 함수
    public static void initSec (ArrayList<Integer> sec, int [] sum){
        for (int i = 1; i < sum.length; i++) {
            for (int j = 0; j < i; j++) {
                sec.add(sum[i]-sum[j]);
            }
        }
    }
    // 본 계산 함수
    public static long calcul(ArrayList<Integer> secA, ArrayList<Integer> secB, int T){
        long ans = 0;
        int a = 0;
        int b = secB.size()-1;

        while ( a < secA.size() && b > -1){
            int now = secA.get(a) + secB.get(b);
            if(now == T){
                // 최초 secA.get(a) 값 혹은 secB.get(b) 값과 같은 값 세어서 중복값 빠르게 처리 위함
                long ac = 0; long bc = 0;
                long firstA = secA.get(a);
                while(a<secA.size() && firstA == secA.get(a)){
                    a++;
                    ac++;
                }

                long firstB = secB.get(b);
                while (b > -1 && firstB == secB.get(b)){
                    b--;
                    bc++;
                }
                ans += (ac * bc);
            }else if(now < T){
                a++;
            }else {
                b--;
            }
        }
        return ans;
    }
}

해당 풀이에서 따로 설명해야할 파트는 아마도 같은 A,B 조합을 만났을 때 어떻게 다루는가? 일 것이다.

위 그림과 같은 경우이다. 주의해야할 점은, 이 중복되는 조합 사이에서 나올 수 있는 경우의 수가 여러가지 이다. 라는 점이다.

맨 왼쪽 2로 타겟값 9를 만드는 경우의 수는 5가지이다. 이는 나머지 2모두 동일하다. 따라서 T를 만들 수 있는 중복된 a값과 b값으로 만들 수 있는 타겟의 갯수는 a * b개 이다.

        if(now == T){
            // 최초 secA.get(a) 값 혹은 secB.get(b) 값과 같은 값 세어서 중복값 빠르게 처리 위함
            long ac = 0; long bc = 0;
            long firstA = secA.get(a);
            while(a<secA.size() && firstA == secA.get(a)){
                a++;
                ac++;
            }

            long firstB = secB.get(b);
            while (b > -1 && firstB == secB.get(b)){
                b--;
                bc++;
            }
            ans += (ac * bc);
        }else if(now < T){
            a++;
        }else {
            b--;
        }

따라서 위와 같이 T가 되는 조합을 만났을 경우, a값과 b값이 각각 중복되는지 세어줘야 한다. ac와 bc는 각각 T가 되는 a와 b가 중복되어서 나타는지 이다. 중복될때마다 값을 올린다. 이후, 이들 간의 조합으로 나올 수 있는 T의 개수를 세서 더해준다.

4. 배운 것들 🎯

• 초반에 틀렸던 이유: 투 포인터를 단방향으로만 생각했다.
  하지만 배열이 두 개이기 때문에 단방향 투 포인터로 풀면 A값이 갱신될 때마다 B값은 처음부터 시작해야한다. (T가 어디서 나올지 예측 불가능해서) 이는 그냥 4중 반복문 완전탐색이 된다.
• 이후 틀렸던 이유: 중복되는 값의 조합이 나올 떄, ac * bc가 아니라 ac + bc로 풀었다. 연속되는 값들의 경우의 수이므로 더하기가 아닌 곱하기로 풀어야 한다. (고등학교 때 확통 잘했는데 ㅠㅠ)