[백준] 2143 두 배열의 합 #JAVA #이분탐색

[백준] 2143 두 배열의 합 #JAVA

 

---

코드

---

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));

		int[] arrA, arrB;
		int[] subArrA, subArrB;
		StringTokenizer stA,stB;
		long total = 0; // 21억개를 초과하는 경우가 존재
		
		int T = Integer.parseInt(br.readLine());
		int N = Integer.parseInt(br.readLine());
		stA = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(br.readLine());
		stB = new StringTokenizer(br.readLine());
		
		arrA = new int[N];
		arrB = new int[M];
				
		for (int i = 0; i < N; i++) {
			arrA[i] = Integer.parseInt(stA.nextToken());
		}
		for (int i = 0; i < M; i++) {
			arrB[i] = Integer.parseInt(stB.nextToken());
		}
		
		// 배열 A,B로 만들 수 있는 누적합 배열을 구한다.
		//배열 A로 만들 수 있는 누적합 배열 구하기
		int size = 0;
		int idx = 0;
		
		for (int i = 1; i <= N; i++) {
			size += i;
		}
		subArrA = new int[size];
		for (int i = 0; i < N; i++) {
			int sum=0;
			int at = i;
			while (at < N) {
				sum += arrA[at++];
				subArrA[idx++] = sum;
			}
		}
		
		//배열 B로 만들 수 있는 누적합 배열 구하기
		size = 0;
		idx = 0;
		for (int i = 1; i <= M; i++) {
			size += i;
		}
		subArrB = new int[size];
		for (int i = 0; i < M; i++) {
			int sum=0;
			int at = i;
			while (at < M) {
				sum += arrB[at++];
				subArrB[idx++] = sum;
			}
		}
		
		//Arrays.sort(subArrA);
		Arrays.sort(subArrB);
		

		//이분탐색
		for (int num : subArrA) {
			int tar = T - num; // 타겟 숫자
			
			//타겟 숫자의 왼쪽을 찾는다.			
			int left= lower_idx(tar ,subArrB);
            
			//타겟 숫자의 오른쪽을 찾는다.
			int right = upper_idx(tar ,subArrB);
			
			//total에 더한다.
			total +=(right - left);
			
		}
		
		System.out.println(total);
		
	}
	
	private static int lower_idx(int target, int[] arr) {
		
		int st = 0;
		int en = arr.length;
		
		while (st < en) {
			int mid = (st+en)/2;
			
			if(arr[mid] >= target) {
				en=mid;
			}else {
				st = mid+1;
			}
		}
		
		return st;
		
	}
	
	private static int upper_idx(int target, int[] arr) {
		
		int st = 0;
		int en = arr.length;
		
		while (st < en) {
			int mid = (st+en)/2;
			
			if(arr[mid] > target) {
				en=mid;
			}else {
				st = mid+1;
			}
		}
		
		return st;
	
	}
	
}

 

 

풀이

---

1. 배열 A,B의 누적합 배열을 구한다. (-> subArrA, subArrB)
2. 배열 subArrA를 for문을 돌리며 배열subArrB B = T-A 의 값이 있는지 이분탐색을 통해 확인한다.
3. lower_idx와, upper_idx 를 통해 타겟에 맞는 값을 찾는다.

 

주의 사항

---

• 정답인 total 변수는 int가 아닌 long 변수이다.
  • 배열 A,B는 최대 1000개의 값으로 각각 1000!개만큼의 부 배열이 나온다. (subArrA, subArrB의 크기 500500)
  • 모든 배열이 쌍 개수가 맞는다고 하면 500500 X 500500으로 int 자료형의 개수인 21억개를 넘어간다.

 

반례

---

#INPUT
5
3
1 5 3
2 
1 2

#OUTPUT
15

 

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)