백준 2143번 (java) HashMap, 이분탐색

백준 2143번: 두 배열의 합

---

관찰

1. 부 배열은 연속된 부분집합이므로 합을 구할 때 누적합을 이용해서 빠르게 구할 수 있을 거 같다
2. 천개의 배열 + 천개의 배열 일단 누적합으로 각각의 부 배열의 경우의 수가 1000000개씩 나온다..
3. 부 배열의 합 경우의 수는 백만 * 백만..
4. 아이디어 어차피 합이 t인 값만 필요하다 값을 저장해두고 찾아야 하는 값만 찾아보자!

---

정답코드

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

public class Main {
    static int t,n,m;
    static int[] arr1,arr2,sumfix1,sumfix2;
    static HashMap<Long,Long> map1;
    static HashMap<Long,Long> map2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // 정답
        long answer = 0;
        // 입력 받기
        t = Integer.parseInt(br.readLine());
        n = Integer.parseInt(br.readLine());
        arr1 = new int[n+1];
        sumfix1 = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < n+1; i++){
            arr1[i] = Integer.parseInt(st.nextToken());
            sumfix1[i] = sumfix1[i-1] + arr1[i];
        }
        m = Integer.parseInt(br.readLine());
        arr2 = new int[m+1];
        sumfix2 = new int[m+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < m+1; i++){
            arr2[i] = Integer.parseInt(st.nextToken());
            sumfix2[i] = sumfix2[i-1] + arr2[i];
        }
        // 부 배열의 합 경우들 map에 담아주기
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n+1;j++){
                long sum = sumfix1[j] - sumfix1[i];
                if(map1.containsKey(sum)){
                    map1.put(sum,map1.get(sum)+1);
                }
                else{
                    map1.put(sum, 1L);
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m+1;j++){
                long sum = sumfix2[j] - sumfix2[i];
                if(map2.containsKey(sum)){
                    map2.put(sum,map2.get(sum)+1);
                }
                else{
                    map2.put(sum, 1L);
                }
            }
        }
        // map1 을 순회하면서 값을 찾으면 서로의 값 곱하기
        Iterator<Long> it = map1.keySet().iterator();
        while(it.hasNext()){
            long cur = it.next();
            long find = t - cur;
            if(map2.containsKey(find)){
                answer += map1.get(cur) * map2.get(find);
            }
        }
        // 출력
        System.out.println(answer);
    }
}

---

풀이

1. 각각의 누적합을 구해준다.
2. 해시맵에다가 부 배열의 합 경우의 수들을 각각 저장해준다!
3. 첫번째 해시맵을 순회하면서 t를 만들 수 있는 두번째 해시맵의 값을 찾는다
4. 값을 찾으면 두 값을 곱한 것이 경우의 수!

---

다른 풀이

풀고 나서 알고리즘을 보는데 이분탐색이 있길래 다른 풀이들을 찾아봤는데 값을 배열에 넣어준 후 sort하여 이분탐색으로 upperBound lowerBound의 차이로 각각의 경우의 수를 구해서 푸는 방법을 봤다

그래서 연습해볼겸 나도 이분탐색으로 풀어봤당

---

이분탐색 정답 코드

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

public class Main {
    static int t,n,m,idx;
    static int[] arr1,arr2,sumfix1,sumfix2;
    static ArrayList<Long> map1;
    static ArrayList<Long> map2;
    static TreeSet<Integer> set;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // 정답
        long answer = 0;
        // 입력 받기
        t = Integer.parseInt(br.readLine());
        n = Integer.parseInt(br.readLine());
        arr1 = new int[n+1];
        sumfix1 = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < n+1; i++){
            arr1[i] = Integer.parseInt(st.nextToken());
            sumfix1[i] = sumfix1[i-1] + arr1[i];
        }
        m = Integer.parseInt(br.readLine());
        arr2 = new int[m+1];
        sumfix2 = new int[m+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < m+1; i++){
            arr2[i] = Integer.parseInt(st.nextToken());
            sumfix2[i] = sumfix2[i-1] + arr2[i];
        }
        // 부 배열의 합 경우들 map에 담아주기
        map1 = new ArrayList<>();
        map2 = new ArrayList<>();
        idx = 0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n+1;j++){
                map1.add((long) (sumfix1[j] - sumfix1[i]));
            }
        }
        idx = 0;
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m+1;j++){
                map2.add((long) (sumfix2[j] - sumfix2[i]));
            }
        }
        map1.sort(Comparator.naturalOrder());
        map2.sort(Comparator.naturalOrder());
        // map1 을 순회하면서 값을 찾으면 서로의 값 곱하기
        for(int i=0;i<map1.size();){
            long cur = map1.get(i);
            long find = t - cur;
            int diff1 = upperBound(map1,cur) - lowerBound(map1,cur);
            int diff2 = upperBound(map2,find) - lowerBound(map2,find);
            answer += (long) diff1 * diff2;
            i += diff1;
        }
        // 출력
        System.out.println(answer);
    }

    private static int lowerBound(ArrayList<Long> map, long find) {
        int answer = map.size();
        int l = 0;
        int r = map.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(map.get(mid) < find){
                l = mid + 1;
            }
            else{
                r = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }

    private static int upperBound(ArrayList<Long> map, long find) {
        int answer = map.size();
        int l = 0;
        int r = map.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(map.get(mid) <= find){
                l = mid+1;
            }
            else{
                answer = mid;
                r = mid - 1;
            }
        }
        return answer;
    }
}

---

느낀점

이분탐색으로 푸는데 시간이 더 오래 걸렸다..😢 그리고 속도도 더 느리고..🥹
왜 이분탐색을 공부해야할까..?

---

이분탐색을 공부해야 하는 이유

곰곰히 생각해보다가 바보 같은 생각이었던 것을 알게됐다

특강 5주차 (이분탐색)

내가 정리해 놓고 깜빡하고 있었다. 가장 큰 이유는 Parametric Search (매개변수 탐색) 같은 고급 알고리즘 단계에서 가장 핵심이 되는 개념이 이분탐색이다!

또한 라이브러리를 사용해서 푸는 것은 한계가 있고 진짜 실력이 아니다..

다음 포스팅은 파라메트릭 서치를 풀어보자..!