[백준] 7453 합이 0인 네 정수 - JAVA

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

 

7453번: 합이 0인 네 정수

 

⏰엄청난 시간초과 늪에 빠졌던 문제 .. 

배열 4개를 하나씩 따지면 시간초과 발생한다. 배열의 크기가 4000까지기 때문에 다 0일경우 대참사.

A+B저장한 배열은 탐색을 안할거라서 정렬을 안했더니 시간초과가 났다. 근데 정렬해주니까 안났다.. 왜 ? 지 ? 

 

 

💡Upper_bound, Lower_bound 참고 

[Algorithm/Java] Lower bound, Upper bound

 

알고리즘

• A+B 저장한 배열, C+D 저장한 배열로 나누어서 두개의 배열로 풀기 
• 단순 이진탐색으로 접근하면, 중복값 처리가 어려울 수 있다. 
• 즉, Upper Bound와 Lower Bound를 사용해서 중복값 처리하며 문제 접근. 

---

 

 

구현 과정

• ab[] : 주어진 A배열과 B배열의 합 (N*N) 
• cd[] : 주어진 C배열과 D배열의 합 (N*N)

 

1. a와 b를 더하여 ab배열에 저장, c와 d를 더하여 cd배열에 저장한다. 

 

2. ab배열과 cd배열 "둘다" 오름차순 정렬한다. (ab는 이분탐색을 할 필요가 없어 정렬하지 않았더니 시간초과 발생)

 

3. 정렬된 ab배열에서 하나씩 꺼내며 ab값과 더해서 0이 되는 cd 값을 찾는다. 즉, ab * (-1) 찾기 

 

4. cd에 ab*(-1) 인 값이 여러개 중복되어 있을 수 있으므로 Upper Bound 와 Lower Bound 인덱스를 찾는다. 

• Upper Bound : 찾고자 하는 값 (ab * (-1)) 보다 큰 값이 처음으로 나타나는 위치 
• Lower Bound : 찾고자 하는 값 (ab * (-1)) 보다 크거나 같은 값 (=이상의 값) 이 처음으로 나타나는 위치 

 

5. Upper Bound - Lower Bound 는 찾고자 하는 값이 없을 경우 0, 있을 경우 몇개 중복되어 있는지 알아낼 수 있다. (찾고자 하는 값이 없을 경우에는 Upper Bound == Lower Bound)

 

6. 합이 0이 되는 쌍의 갯수를 저장할 변수 count 는 long 타입으로 설정해준다. (배열의 크기 n이 4000일 경우 ab와 cd 의 크기는 16,000,000 이고 모든 값이 0으로 주어질 경우 count의 갯수는 16,000,000 x 16,000,000 = 256,000,000,000,000 으로 int형의 범위를 훨씬 넘는다.)

---

 

소스 코드 

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

public class Solution_BaekJoon_7453 {
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		int n = Integer.parseInt(br.readLine()); 
		int a[]= new int[n];
		int b[]= new int[n];
		int c[]= new int[n];
		int d[]= new int[n]; 
		
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(br.readLine(), " "); 
			a[i]= Integer.parseInt(st.nextToken());
			b[i]= Integer.parseInt(st.nextToken());
			c[i]= Integer.parseInt(st.nextToken());
			d[i]= Integer.parseInt(st.nextToken());
		}
		
		//a와 b를 더하고 c와 d를 더하기 
		int[] ab= new int[n*n];
		int[] cd= new int[n*n];
		int index=0; 
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				ab[index] = a[i]+b[j]; 
				cd[index++] = c[i]+d[j];
			}
		}
	
		Arrays.sort(ab);
		Arrays.sort(cd);

		long count=0; //합이 0이 되는 쌍의 갯수 
		for(int i=0; i<ab.length; i++) {
			int find = ab[i] * (-1); //cd에서 찾아야 하는 값 

			int upper = UpperBound(cd, find);
			int lower = LowerBound(cd, find);
			count+=(upper-lower); 
		}
		
		System.out.println(count);
		
	}//end of main

	private static int UpperBound(int[] cd, int find) {
		int left=0; 
		int right=cd.length;
		while(left<right) {
			int mid=(left+right)/2;
			
			if(cd[mid] <= find) left=mid+1;
			else right=mid; 
		}
		return right;
	}

	private static int LowerBound(int [] cd, int find) {
		int left=0;
		int right=cd.length;
		
		while(left<right) {
			int mid=(left+right)/2;
			if(cd[mid] < find) left=mid+1; 
			else right=mid; 
		}
		return right; 
	}
}//end of class