백준 2143번 두 배열의 합 (Java)

해결 과정

두 배열이 주어지면 각 배열마다 부 배열의 합이 있을 것이고, 특정 부 배열의 합들을 더해서 T를 만족하는 경우의 수를 구하는 문제다. 문제에서 주어졌듯이 부 배열은 각 배열에서 매우 많다. (단, 입력의 조건에 의해 최대 배열의 길이는 1000이므로 배열 당 최대 1000000개까지 나올 것이다) 부 배열은 연속된 배열이라는 특징이 있다.

가장 먼저 눈에 띄는 것은 T의 범위인데 범위가 매우 커서 int로 담을 수 없다는 것을 바로 알 수 있다. 따라서 문제 해결 과정에서 필요한 곳에 long 타입을 사용해야한다. 또한 단순히 모든 부 배열의 쌍을 구한다면 1000000 * 1000000 번의 연산이 필요하기 때문에 시간초과가 발생할 것이다. 따라서 다른 방법으로 접근해야한다.

 

이 문제는 경우의 수를 구하는 것이다. 따라서, 모든 쌍에 대해서 알아야할 필요는 없다. 따라서, 각 배열의 부 배열이 만들 수 있는 합을 모두 구하고 그 합끼리 계산을 통해 경우의 수를 도출해 낼 수 있을 것이다.

각 배열마다 부 배열이 만들 수 있는 합을 구하는 것은 연산량에서 문제가 되지 않는다. 어차피 배열의 길이는 1000으로 제한되있고, O(n^2)의 연산으로 돌렸을 때, 1000000번의 연산안에 해결할 수 있다.

 

하지만 구한 부 배열의 합에서 다시 단순히 반복문을 통해 모든 리스트를 순회하면 앞서 말한 것과 크게 다르지 않다. 따라서 다른 방법이 필요하다. A 배열의 특정 부 배열의 합의 값을 선택하고, B 배열의 부 배열의 합을 찾는 것은 특정 Value를 찾는 것과 같다. 따라서, Binary Search를 통해 값을 찾을 수 있는데, 문제는 동일한 값이 여러번 나올 수 있다는 것. 이 부분에서 얼마전 풀었던 Leetcode의 Combination Sum 문제가 생각이 났다. Binary Search를 조금만 변형하면 Upper Bound와 Lower Bound를 찾을 수 있다.

따라서 이러한 알고리즘들을 구현하면 문제를 해결할 수 있다.

+ Binary Search말고 투 포인터로 해결하는 방법도 있다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long t = scanner.nextInt();
        int n = scanner.nextInt();
        int[] a = new int[n];

        for (int i=0; i<n; i++) {
            a[i] = scanner.nextInt();
        }

        int m = scanner.nextInt();
        int[] b = new int[m];

        for (int i=0; i<m; i++) {
            b[i] = scanner.nextInt();
        }

        ArrayList<Long> aList = new ArrayList<>();
        ArrayList<Long> bList = new ArrayList<>();

        calculateSumOfSequence(aList, a);
        calculateSumOfSequence(bList, b);

        Collections.sort(bList);

        long count = 0;
        for (long num : aList) {
            count += calculateRangeOfValidValue(t-num, bList);
        }

        System.out.println(count);
    }

    static void calculateSumOfSequence(ArrayList<Long> list, int[] numList) {
        for (int i=0; i<numList.length; i++) {
            long sum = 0;
            for (int j=i; j<numList.length; j++) {
                sum += numList[j];
                list.add(sum);
            }
        }
    }

    static int calculateRangeOfValidValue(long target, ArrayList<Long> b) {
        int left = 0;
        int right = 0;

        int start = 0;
        int end = b.size()-1;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (b.get(mid) >= target) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }

        left = end;
        start = 0;
        end = b.size()-1;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (b.get(mid) <= target) {
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        right = end;

        return right - left;
    }
}

 

https://leetcode.com/problems/combination-sum/

Combination Sum - LeetCode