[PS] 백준2143 : 두 배열의 합(Java)

문제

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

2143번: 두 배열의 합

---

풀이

누적합 및 자료구조를 활용한 풀이

접근법

1. A수열과 B수열에서 나올 수 있는 모든 부 배열을 누적합을 활용하여 구함
2. Map 자료구조를 활용하여 해당 누적합 값이 기존에 들어가있다면 value증가, 없다면 put
3. A의 부 배열 개수만큼 반복문을 돌면서 목표값 T - A[i](부 배열 원소) 값이 B 부 배열 Map에 있는지 확인.
4. 있다면 해당 개수를 결과값에 누적 증가

조금 더 풀어서 설명해보자면

각 수열의 최대입력은 1,000으로 모든 부 배열의 경우의 수는 500,500이다.

2개의 수열을 각각의 Map을 활용해서 관리하면 총 100만개의 Map 데이터가 생성된다.

 

Map으로 관리할 값은 Key에 부분 배열의 합, Value에 해당 값의 개수이며,

누적합으로 탐색을 하면서 기존 Map에 같은 값이 있다면 Value를 1증가하고,

기존 Map에 같은 값이 없다면 Value를 1로 새롭게 Put한다.

 

완성된 Map을 통해 A배열의 500,000개를 완전탐색을 통해 목표값 T와 원소값의 차이값을 B Map에서 찾아 해당 값의 개수를 결과에 누적하는 식으로 풀이를 진행했다.

 

---

소스코드

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

    //BOJ_2143 두 배열의 합
    public class Main {
        static int N;
        static long res;
        static int[] a, b;
        static long[] na, nb;
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;

            HashMap<Long, Integer> B_data = new HashMap<>();

            na = new long[500600];
            nb = new long[500600];
            N = Integer.parseInt(br.readLine());

            int lengA = Integer.parseInt(br.readLine());
            a = new int[lengA];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<lengA; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            int lengB = Integer.parseInt(br.readLine());
            b = new int[lengB];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<lengB; i++) {
                b[i] = Integer.parseInt(st.nextToken());
            }

            //A 누적합을 전부 계산
            int p = 0;
            int naCnt = 0;
            for(int i=0; i<lengA; i++) {
                for(int j=i; j<lengA; j++) {
                    if(i==j) {
                        //초기화
                        na[p++] = a[i];
                    }
                    else {
                        na[p++] = na[p-2] + a[j];
                    }
                    System.out.print(na[p-1] + " ");
                    naCnt++;
                }
            }

            //B 누적합을 전부 계산
            p = 0;
            for(int i=0; i<lengB; i++) {
                for(int j=i; j<lengB; j++) {
                    if(i==j) {
                        //초기화
                        nb[p++] = b[i];
                    }
                    else {
                        nb[p++] = nb[p-2] + b[j];
                    }
                    if(B_data.get(nb[p-1]) != null) {
                        int idx = B_data.get(nb[p-1]);
                        B_data.put(nb[p-1], ++idx);
                    }
                    else B_data.put(nb[p-1], 1);
                }
            }

            for(int i=0; i<naCnt; i++) {
                long idx = na[i];
                long key = N - idx;
                if(B_data.get(key) != null) {
                    res += B_data.get(key);
                }
            }

            System.out.println(res);

        }
    }

 

---

정리

 

첫번째 접근에서 메모리 제한이 64MB인걸 보고 최대한 작은 메모리를 사용해야겠다 생각하고 모든 부 배열의 값을 저장하려는 생각을 하지 못함.. 100만개를 저장하면 당연히 터지지 않을까 생각한게 오류..

 

이 후 질문 게시판을 뒤적이다가 내 접근법과 비슷한 풀이가 있길래 봤는데 놀랍게도 100만개를 Map에 전부 넣고 완전탐색을 수행하는 코드가 Accept를 받았길래 메모리초과가 안나는걸 확인하여 기존 풀이에서 조금 변경해서 풀어서 Accept를 받아냄…

 

이전 포스팅에서도 long Type때문에 억장 와르르 였는데 이번에도 마찬가지로 결과값은 21억을 넘어가지 않을거라 생각하고 int형으로 사용했다가 68%틀…

 

이번 문제의 교훈으로

1.공간복잡도 다시 정리하자… 제대로 계산도 못하는건 문제가 있잖아!

2.자나깨나 Type조심하자!!..