백준 2143 두 배열의 합 - JAVA

2143 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<HashMap 풀이>

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // HashMap 풀이
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        long T = Long.parseLong(br.readLine());
        
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        } 
        
        int m = Integer.parseInt(br.readLine());
        int[] b = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        } 
        
        HashMap<Long, Integer> aSum = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                aSum.put(sum, aSum.getOrDefault(sum, 0) + 1);
            } 
        }
        long count = 0;
        for (int i = 0; i < m; i++) {
            long sum = 0;
            for (int j = i; j < m; j++) {
                sum += b[j];
                if (aSum.containsKey(T - sum)) {
                    count += aSum.get(T - sum);
                } 
            } 
        }
        bw.write(String.valueOf(count));
        bw.flush();
    }
}

 

<Tow-pointer 풀이>

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        long T = Integer.parseInt(br.readLine());
        
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        } 
        
        int m = Integer.parseInt(br.readLine());
        int[] b = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        } 
        
        long[] aSum = new long[n*(n+1) / 2];
        long[] bSum = new long[m*(m+1) / 2];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                aSum[idx++] = sum;
            } 
        }
        idx = 0;
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = i; j < m; j++) {
                sum += b[j];
                bSum[idx++] = sum;
            } 
        }
        bw.write(String.valueOf(TwoPointer(T, aSum, bSum)));
        bw.flush();
    }
    private static long TwoPointer(long T, long[] aSum, long[] bSum) {
        Arrays.sort(aSum);
        Arrays.sort(bSum);
        int left = 0;
        int right = bSum.length - 1;
        long count = 0;
        while(left < aSum.length && right > -1) {
            long asv = aSum[left], bsv = bSum[right];
            long sum = aSum[left] + bSum[right];
            if(sum == T) {
                long aSumCount = 0;
                long bSumCount = 0;
                while(left < aSum.length && asv == aSum[left]) {
                    left++;
                    aSumCount++;
                }
                while (right > -1 && bsv == bSum[right]) {
                    right--;
                    bSumCount++;
                }
                count += (aSumCount * bSumCount);
            } else if (sum < T) {
                left++;
            } else {
                right--;
            }
        }
        return count;
    }
}

 

<이분탐색 풀이>

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        long T = Integer.parseInt(br.readLine());
        
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        } 
        
        int m = Integer.parseInt(br.readLine());
        int[] b = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        } 
        
        long[] aSum = new long[n*(n+1) / 2];
        long[] bSum = new long[m*(m+1) / 2];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                aSum[idx++] = sum;
            } 
        }
        idx = 0;
        for (int i = 0; i < m; i++) {
            int sum = 0;
            for (int j = i; j < m; j++) {
                sum += b[j];
                bSum[idx++] = sum;
            } 
        }
        Arrays.sort(aSum);
        long result = 0;
        for (long i : bSum) {
            long target = T - i;
            result += countRange(aSum, target);
        } 
        bw.write(String.valueOf(result));
        bw.flush();
    }
    private static long countRange(long[] aSum, long target) {
        long lower = lowerBound(aSum, target);
        long upper = upperBound(aSum, target);
        return upper - lower;
    }
    private static long lowerBound(long[] aSum, long target) {
        int low = 0;
        int high = aSum.length;
        while(low < high) {
            int mid = (low + high) / 2;
            if (aSum[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    private static long upperBound(long[] aSum, long target) {
        int low = 0;
        int high = aSum.length;
        while(low < high) {
            int mid = (low + high) / 2;
            if (aSum[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

 

알고리즘 설명

---

이번 문제는 풀 수 있는 알고리즘이 상당히 많습니다. 제가 풀 수 있는 방식만해도 HashMap, Two-pointer, 이분탐색(UpperBound, LowerBound), 기본적인 이분탐색 까지 총 네개입니다. 더 있을 수도 있지만... 기본적인 이분탐색에 비해, UpperBound/LowerBound방식이 효율적인 방식이기 때문에 저는 HashMap, Tow-pointer, 이분탐색(UpperBound, LowerBound) 이렇게 총 세 가지 알고리즘을 다뤄보겠습니다.

 

먼저 HashMap입니다. a 배열의 부분배열 합을 구하여 HashMap(key: 부분배열 합, value: 그 합이 나타난 횟수)에 저장합니다. 이후, B 배열의 부분배열 합을 구한 후, 해당 합에 대해 T - 합이 A 배열의 부분배열 합으로 존재하는지 HashMap에서 확인하고, 해당 키의 밸류를 count에 누적합하여 결과를 출력하는 방식입니다.

 

남은 두 알고리즘은 n의 입력줄을 a배열, m의 입력줄을 b배열로 받아 저장하고, 배열의 부분배열을 구하는 공식이(N * (N+1)) / 2 이기 때문에, 배열의 크기를 (N * (N+1)) / 2로 설정합니다.

 

투 포인터 알고리즘은, aSum과 bSum을 오름차순으로 정렬한 뒤, left포인터는 aSum배열의 왼쪽, right 포인터는 bSum배열의 오른쪽 끝에서 시작하여, 두 포인터가 가리키는 값의 합이 목표 값 T와 일치하면 중복된 값들을 처리하여 그 경우를 카운트합니다. 합이 목표 값보다 작으면 왼쪽 포인터를 이동시키고, 크면 오른쪽 포인터를 이동시켜 탐색을 계속합니다. 탐색이 종료되면 count를 반환합니다.

 

UpperBound와 LowerBound를 활용한 이분탐색은 aSum 배열을 오름차순으로 정렬하고, 각 bSum의 값에 대해 목표 값 T에서 해당 값을 뺀 값을 aSum에서 찾기 위해 이분 탐색을 사용합니다. 이때, lowerBound를 사용하여 aSum에서 목표 값보다 작지 않은 첫 번째 인덱스를 찾고, upperBound를 사용하여 목표 값보다 큰 첫 번째 인덱스를 찾습니다. 그 후, upperBound - lowerBound로 해당 값이 몇 번 등장하는지 계산하여 결과에 더합니다. 이 과정을 반복하여 countRange로 target값과 동일한 배열의 범위를 출력하고 result에 누적합하여 반환합니다.

 

이 세가지 알고리즘의 시간복잡도를 보여드리겠습니다.

 

아래는 각각 HashMap, 투포인터 이분탐색 결과입니다.

아래부터 이분 탐색, 투 포인터, 해시 맵

예상을 해보자면, 투 포인터는 브루트포스방식과 유사하고 해시맵같은 인덱스도 없고, 이분 탐색과 같이 조건에 따라 특정 원소를 제외할 수 있는 것도 아니어서 가장 오래걸리지 않았나 싶습니다. 해시맵은 앞서 말씀드렸다시피, 해시라는 자료구조의 특성상 탐색에 유리할 수 밖에 없는 구조여서 가장 빠른 시간이 걸린것 같습니다. 생각보다 어려운 문제였는데, 이렇게 글 정리까지 하고있으니 성취감이 돋네요

코드 해석

---

1. 해시맵 방식: 먼저 a 배열의 모든 부분배열 합을 구하고, 이를 해시맵에 저장하여 각 합이 나타난 횟수를 기록합니다. 그 후, b 배열의 부분배열 합을 구하면서 T - bSum[i]가 해시맵에 존재하는지 확인하고, 존재할 경우 해당 합이 나타난 횟수를 결과에 더합니다.

 

2. 투 포인터 방식: a 배열과 b 배열의 부분배열 합을 각각 구한 후, 두 배열을 오름차순으로 정렬합니다. 왼쪽 포인터는 aSum, 오른쪽 포인터는 bSum배열에서 시작하여 두 포인터의 합이 목표값 T와 같으면 카운트를 증가시키고, 목표값보다 작으면 왼쪽 포인터를 증가시키며, 크면 오른쪽 포인터를 감소시켜 두 배열을 하나씩 처리합니다.

 

3. 이분탐색 방식: a 배열과 b 배열의 부분배열 합을 각각 구한 후, aSum배열을 오름차순으로 정렬합니다. T - bSum[i]를 target으로 설정하고, UpperBound값과 LowerBound의 값을 각각 구하여, CountRange를 통해 범위안의 target개수를 구합니다. 이분탐색으로 찾은 결과는 모든 부분합에 대해 누적합하여 출력합니다.