BOJ2143 두 배열의 합*

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

2143번: 두 배열의 합

 

이문제는 Map과 이분탐색 두가지 방법으로 풀 수 있다. 

나는 Map이 더 간단해보여 Map을 이용했다.

import java.util.*;
import java.io.*;
public class Main
{   
    



	public static void main(String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //0. 입력
        int t = Integer.valueOf(br.readLine());
        int an = Integer.valueOf(br.readLine());
        String[] temp_a = br.readLine().split(" ");
        int bn = Integer.valueOf(br.readLine());
        String[] temp_b = br.readLine().split(" ");
        int[] a = new int[an];
        int[] b = new int[bn];
        
        for(int i=0;i<an;i++){
            a[i] = Integer.valueOf(temp_a[i]);
        }
        for(int i=0;i<bn;i++){
            b[i] = Integer.valueOf(temp_b[i]);
        }
        
        
        //1-1. 누적합으로 A,B 집합 누적합배열 만들기
        int[] sum_a;
        int[] sum_b;
        
        sum_a = new int[a.length+1];
        sum_b = new int[b.length+1];
        sum_a[0] = 0;
        sum_b[0] = 0;
        for(int i=1; i<a.length+1; i++){
            sum_a[i] = a[i-1] + sum_a[i-1];
        }
        for(int i=1; i<b.length+1; i++){
            sum_b[i] = b[i-1] + sum_b[i-1];
        }
        //1-2. 해쉬맵에 구간합 갯수 넣기
        HashMap<Integer,Long> hash_a = new HashMap();
        HashMap<Integer,Long> hash_b = new HashMap();
        
        for(int i=0;i<sum_a.length-1;i++){
            for(int j=i+1; j<sum_a.length;j++){
                hash_a.put(sum_a[j]-sum_a[i],hash_a.getOrDefault(sum_a[j]-sum_a[i],0l)+1);
            }
        }
        
        for(int i=0;i<sum_b.length-1;i++){
            for(int j=i+1; j<sum_b.length;j++){
                hash_b.put(sum_b[j]-sum_b[i],hash_b.getOrDefault(sum_b[j]-sum_b[i],0l)+1);
            }
        }
        
        // 2. T-A누적합이 B누적합에 있는지 이진탐색 후 갯수 체크
        // 2. 또는 해쉬맵 이용
        long ans = 0;
        for(int key : hash_a.keySet()){
            ans+= hash_a.get(key)*hash_b.getOrDefault(t-key,0l);
        }
        

		System.out.println(ans);
	}
}

 

 

MAP

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Main
{
    static Map<Integer, Integer> getAllPartSumCount(int[] arr) {
        int N = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = i; j < N; j++) {
                sum += arr[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        return map;
    }

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

        int T = sc.nextInt();
        int N = sc.nextInt();
        int[] arr1 = new int[N];
        for (int i = 0; i < N; i++)
            arr1[i] = sc.nextInt();

        int M = sc.nextInt();
        int[] arr2 = new int[M];
        for (int i = 0; i < M; i++)
            arr2[i] = sc.nextInt();

        Map<Integer, Integer> partSum1 = getAllPartSumCount(arr1);
        Map<Integer, Integer> partSum2 = getAllPartSumCount(arr2);

        long ans = 0;
        for (Map.Entry<Integer, Integer> entry : partSum1.entrySet()) {
            int sum = entry.getKey();
            int count = entry.getValue();
            ans += (long)count * partSum2.getOrDefault(T - sum, 0);
        }
        System.out.println(ans);
    }
}

 

 

 

이분탐색

경계 부분을 찾는다.

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static int findLowerBoundIndex(int[] arr, int x) {
        // x 이상의 값이 처음으로 나타나는 위치
        int lowerBoundIndex = arr.length;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else {
                r = m - 1;
                lowerBoundIndex = m;
            }
        }
        return lowerBoundIndex;
    }

    static int findUpperBoundIndex(int[] arr, int x) {
        // x 초과의 값이 처음으로 나타나는 위치
        int upperBoundIndex = arr.length;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] <= x) l = m + 1;
            else {
                r = m - 1;
                upperBoundIndex = m;
            }
        }
        return upperBoundIndex;
    }

    static int[] getAllPartSum(int[] arr) {
        int N = arr.length;
        int[] partSum = new int[N * (N + 1) / 2];
        int partSumIndex = 0;
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = i; j < N; j++) {
                sum += arr[j];
                partSum[partSumIndex++] = sum;
            }
        }
        return partSum;
    }

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

        int T = sc.nextInt();
        int N = sc.nextInt();
        int[] arr1 = new int[N];
        for (int i = 0; i < N; i++)
            arr1[i] = sc.nextInt();

        int M = sc.nextInt();
        int[] arr2 = new int[M];
        for (int i = 0; i < M; i++)
            arr2[i] = sc.nextInt();

        int[] partSum1 = getAllPartSum(arr1);
        int[] partSum2 = getAllPartSum(arr2);

        Arrays.sort(partSum2);

        long ans = 0;
        for (int sum1 : partSum1) {
            int pairSum = T - sum1;
            int lowerBoundIndex = findLowerBoundIndex(partSum2, pairSum);
            int upperBoundIndex = findUpperBoundIndex(partSum2, pairSum);
            ans += upperBoundIndex - lowerBoundIndex;
        }
        System.out.println(ans);
    }
}