[백준] 2143: 두 배열의 합 - JAVA

in Algorithm on 자료 구조

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

풀이

배열 2개가 주어지고 배열들의 부 배열들을 합하여 T를 만들는 경우의 수를 찾는 문제이다.

두 가지 방법으로 풀 수 있는 문제였다.

첫 번째로 생각한 방법은 Map을 사용해 containsKey를 이용하는 방법이었다.

배열 A의 부 배열들의 합을 map에 저장해 놓는다.

배열 B의 부 배열의 합을 구하면서 T에서 뺀 값이 A의 map에 있다면 map의 value 만큼 카운트하여 더해준다.

이 방법으로 제출하고 다른 풀이들을 보니 이분 탐색으로 푸는 방법도 있었다.

List에 부 배열들을 저장하고 이분 탐색을 위해 정렬한다.

ListA에서 값을 꺼내면서 T - 꺼낸 값을 찾을 값으로 하여 ListB에서 이분탐색을 통해 찾는다.

개수가 여러 개 있을 수 있으므로 키값이 처음으로 나오는 인덱스와 키값보다 처음으로 커지는 인덱스를 찾아 두 수의 차이를 개수로 하여 더해준다.

Map

메모리: 58104KB

시간: 388ms

언어: Java 11

코드

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

public class Main {
    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arrA[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());
        int[] arrB = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            arrB[i] = Integer.parseInt(st.nextToken());
        }

        Map<Integer, Integer> mapA = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int sum = 0;
            for(int j = i; j < n; j++) {
                sum += arrA[j];
                mapA.put(sum, mapA.getOrDefault(sum, 0) + 1);
            }
        }

        long ans = 0;
        for(int i = 0; i < m; i++) {
            int sum = 0;
            for(int j = i; j < m; j++) {
                sum += arrB[j];
                int key = T - sum;
                if(mapA.containsKey(key)) {
                    ans += mapA.get(key);
                }
            }
        }

        System.out.println(ans);
    }

}

List + 이분 탐색

메모리: 47800KB

시간: 908ms

언어: Java 11

코드

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

public class Main {
    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arrA[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());
        int[] arrB = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arrB[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> listA = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arrA[j];
                listA.add(sum);
            }
        }

        List<Integer> listB = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = i; j < m; j++) {
                sum += arrB[j];
                listB.add(sum);
            }
        }

        // Collections.sort(listA);
        Collections.sort(listB);

        long ans = 0;
        for (int sumA : listA) {
            int key = T - sumA;
            int lb = lower_bound(key, listB);
            int ub = upper_bound(key, listB);

            ans += (ub - lb);
        }

        System.out.println(ans);
    }

    private static int upper_bound(int key, List<Integer> listB) {
        // key보다 큰 값이 처음으로 나타나는 인덱스

        int left = 0;
        int right = listB.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (listB.get(mid) > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private static int lower_bound(int key, List<Integer> listB) {
        // key와 같은 값이 처음으로 나타나는 인덱스

        int left = 0;
        int right = listB.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (listB.get(mid) >= key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

}