[백준 BOJ / JAVA] 두 배열의 합 (2143번)

📘 1. 문제 소개

2143번: 두 배열의 합

  해당 문제는 이분 탐색과 투 포인터로 풀 수 있다.

 

📘 2. 이분 탐색을 이용한 풀이

🧵 1. 풀이

  간단하게 생각해 보면 다음과 같은 방법을 떠올릴 수 있다.

• A와 B의 부 배열의 합을 구한다.
• A의 부 배열의 합을 반복문으로 돌면서, B의 부 배열의 합에서 이분 탐색을 이용하여 T를 만들 수 있는 값을 찾는다. (물론 B의 부 배열의 합을 기준으로 반복문을 돌아도 된다.)

  하지만, 이렇게 하면 안 된다. 배열에 중복되는 값이 있을 수 있기 때문이다. 그렇기 때문에 단순히 이분탐색으로 값이 있는지 없는지만 찾은 것이 아닌 조건에 충족하는 값이 몇 개가 있는지를 찾아야 한다.

 

  이때 사용할 수 있는 것이 Lower Bound와 Upper Bound다.

• Lower Bound 
  찾고자 하는 값 이상이 처음으로 나타나는 위치
  즉, 찾고자 하는 값이 없는 경우 그 이상의 값이 처음으로 나타나는 위치를 알려준다.
• Upper Bound 
  찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치

Lower Bound와 Upper Bound를 이용하여 조건에 충족하는 값의 개수를 찾을 수 있다.

 

🧵 2. 코드

public class Main {

    static int T, N, M;
    static long ansCnt;
    static int[] numsA, numsB, sumA, sumB, partA, partB;
    static String[] ss;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(in.readLine());
        N = Integer.parseInt(in.readLine());
        numsA = new int[N];
        sumA = new int[N + 1];


        ss = in.readLine().split(" ");

        for(int i = 0; i < N; i++) {
            numsA[i] = Integer.parseInt(ss[i]);
            // 누적합
            sumA[i + 1] = sumA[i] + numsA[i];
        }

        // 부 배열의 합
        int temp = 0;
        partA = new int[((N + 1) * (N)) / 2];
        for(int cnt = 1; cnt <= N; cnt++) {
            for(int st = 0; st + cnt <= N; st++) {
                partA[temp++] = sumA[st + cnt] - sumA[st];
            }
        }

        M = Integer.parseInt(in.readLine());
        numsB = new int[M];
        sumB = new int[M + 1];

        ss = in.readLine().split(" ");

        for(int i = 0; i < M; i++) {
            numsB[i] = Integer.parseInt(ss[i]);
            // 누적합
            sumB[i + 1] = sumB[i] + numsB[i];
        }

        // 부 배열의 합
        temp = 0;
        partB = new int[((M + 1) * (M)) / 2];
        for(int cnt = 1; cnt <= M; cnt++) {
            for(int st = 0; st + cnt <= M; st++) {
                partB[temp++] = sumB[st + cnt] - sumB[st];
            }
        }

        Arrays.sort(partA);
        Arrays.sort(partB);

        // 1. 이분 탐색을 이용하는 방법
        for(int i = 0; i < partA.length; i++) {
            int aValue = partA[i];
            int bValue = T - aValue;

            // bValue에 해당하는 값의 개수를 구하기
            int bValueCnt = upperBound(partB, bValue) - lowerBound(partB, bValue);

            ansCnt += bValueCnt;
        }

        System.out.println(ansCnt);
    }

    private static int lowerBound(int[] arr, int key) {
        int l = 0;
        int r = arr.length;

        while(l < r) {
            int mid = (l + r) / 2;
            if(arr[mid] < key)
                l = mid + 1;
            else
                r = mid;
        }

        return r;
    }

    private static int upperBound(int[] arr, int key) {
        int l = 0;
        int r = arr.length;

        while(l < r) {
            int mid = (l + r) / 2;
            if(arr[mid] <= key)
                l = mid + 1;
            else
                r = mid;
        }

        return r;
    }
}

 

📘 3. 투 포인터를 이용한 풀이

🧵 1. 풀이

  결국 A의 부 배열의 값과 B의 부 배열의 값을 더하는 것이므로 투 포인터를 활용할 수 있다. 부 배열을 정렬한 후, A는 제일 왼쪽에서 시작하고 B는 제일 오른쪽에서 시작하면 된다. (반대 방향도 가능하다.)

  그리고 각 포인터의 합이 T보다 작은 경우 A를 오른쪽으로, T보다 큰 경우 B를 왼쪽으로 이동하면 된다. 합이 T인 경우에는 단순히 카운트를 +1만 해주는 것이 아니라, 중복된 값이 몇 개 있는지 확인하여 그에 해당하는 값을 cnt에 더해줘야 한다.

 

🧵 2. 코드

public class Main {

    static int T, N, M;
    static long ansCnt;
    static int[] numsA, numsB, sumA, sumB, partA, partB;
    static String[] ss;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(in.readLine());
        N = Integer.parseInt(in.readLine());
        numsA = new int[N];
        sumA = new int[N + 1];


        ss = in.readLine().split(" ");

        for(int i = 0; i < N; i++) {
            numsA[i] = Integer.parseInt(ss[i]);
            // 누적합
            sumA[i + 1] = sumA[i] + numsA[i];
        }

        // 부 배열의 합
        int temp = 0;
        partA = new int[((N + 1) * (N)) / 2];
        for(int cnt = 1; cnt <= N; cnt++) {
            for(int st = 0; st + cnt <= N; st++) {
                partA[temp++] = sumA[st + cnt] - sumA[st];
            }
        }

        M = Integer.parseInt(in.readLine());
        numsB = new int[M];
        sumB = new int[M + 1];

        ss = in.readLine().split(" ");

        for(int i = 0; i < M; i++) {
            numsB[i] = Integer.parseInt(ss[i]);
            // 누적합
            sumB[i + 1] = sumB[i] + numsB[i];
        }

        // 부 배열의 합
        temp = 0;
        partB = new int[((M + 1) * (M)) / 2];
        for(int cnt = 1; cnt <= M; cnt++) {
            for(int st = 0; st + cnt <= M; st++) {
                partB[temp++] = sumB[st + cnt] - sumB[st];
            }
        }

        Arrays.sort(partA);
        Arrays.sort(partB);

        // 2. 투 포인터를 활용하는 방법
        int aLeft = 0;
        int bRight = partB.length - 1;
        while(aLeft < partA.length && 0 <= bRight) {
            int aValue = partA[aLeft];
            int bValue = partB[bRight];

            if(aValue + bValue == T) {
                // 중복된 값들을 카운트
                long aCnt = 0L;
                long bCnt = 0L;
                while(aLeft < partA.length && aValue == partA[aLeft]) {
                    aLeft++;
                    aCnt++;
                }
                while(0 <= bRight && bValue == partB[bRight]) {
                    bRight--;
                    bCnt++;
                }

                ansCnt += aCnt * bCnt;
            }
            else if(aValue + bValue < T) {
                aLeft++;
            }
            else {
                bRight--;
            }
        }

        System.out.println(ansCnt);
    }
}