[BOJ] 2143 두 배열의 합 - JAVA

1. 문제

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

---

2. 풀이

이분탐색버전

가능한 부분합 더하기

list, size를 파라미터로 받아서 가능한 부분합을 모두 추가한다.

public static void add(List<Integer> list, int size){
   int sum;
   for(int i=0;i<size;i++){
      sum = list.get(i);
      for(int j=i+1;j<size;j++){
         sum += list.get(j);
         list.add(sum);
      }
   }
}

 

list에서 x가 있는 첫 번째 위치 구하기

이분탐색을 이용한다.

public static int lower_bound(List<Integer> list, int x){
   int l = 0, r = list.size(), m;
   while(l<r){
      m = (l+r)/2;
      if(list.get(m)>=x) r = m;
      else l = m+1;
   }
   return l;
}

 

list에서 x를 초과하는 첫 번째 위치 구하기

위와 비슷한 방식이되, 5번째 줄의 부등호만 변경한다. r을 반환한다.

public static int upper_bound(List<Integer> list, int x){
   int l = 0, r = list.size(), m;
   while(l<r){
      m = (l+r)/2;
      if(list.get(m)>x) r = m;
      else l = m+1;
   }
   return r;
}

 

Main

1.  ArrayList A,B에 각각 입력받고, 가능한 부분합을 더한다.

2.  B만 정렬한다.

3.  A의 원소를 하나씩 탐색한다. B에서 T-원소의 lower bound, upper bound를 찾는다. 

4.  answer에 u-l을 더한다. (중복원소 개수를 더하는 것이다)

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   int N = Integer.parseInt(in.readLine());
   ArrayList<Integer> A = new ArrayList<>();
   StringTokenizer st = new StringTokenizer(in.readLine());
   for(int i=0;i<N;i++) A.add(Integer.parseInt(st.nextToken()));
   int M = Integer.parseInt(in.readLine());
   ArrayList<Integer> B = new ArrayList<>();
   st = new StringTokenizer(in.readLine());
   for(int i=0;i<M;i++) B.add(Integer.parseInt(st.nextToken()));

   //가능한 부분합 집합
   add(A,N);
   add(B,M);

   Collections.sort(B);

   long answer = 0;
   int l, u;
   for(int a:A){
      l = lower_bound(B,T-a);
      u = upper_bound(B,T-a);
      answer += u-l;
   }

   System.out.println(answer);
}

 

Map버전

1.  모두 입력받은 뒤, 위의 add함수처럼 list에 부분합을 더하는 것이 아니라 map에 put한다. key는 부분합, value는 카운트다. 따라서 getOrDefault를 자주 활용한다!

2.  map에 모든 부분합을 추가했다면 B의 가능한 부분합을 구해가면서 map에 T-B원소가 있는지 찾아낸다. 있다면 answer에 그 값을 더한다.

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

public class BOJ_2143_두배열의합2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      int N = Integer.parseInt(in.readLine());
      int[] A = new int[N];
      Map<Integer, Integer> Amap = new HashMap<>();
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) A[i] = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(in.readLine());
      int[] B = new int[M];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<M;i++) B[i] = Integer.parseInt(st.nextToken());

      int sum;
      for(int i=0;i<N;i++) {
         sum = A[i];
         Amap.put(sum,Amap.getOrDefault(sum,0)+1);
         for(int j=i+1;j<N;j++){
            sum += A[j];
            Amap.put(sum,Amap.getOrDefault(sum,0)+1);
         }
      }

      long answer = 0;
      for(int i=0;i<M;i++){
         sum = B[i];
         answer += Amap.getOrDefault(T-sum,0);
         for(int j=i+1;j<M;j++){
            sum += B[j];
            answer += Amap.getOrDefault(T-sum,0);
         }
      }

      System.out.println(answer);
   }


}

 

---

3. 결과

이분탐색 범위때문에 계속 틀렸다. 누적합 다음에 dp가 아니라 이분탐색을 풀어야할지 고민된다.

시간이 더 많이 걸린게 이분탐색, 적게 걸린게 map을 사용한 것이다.