[BOJ] 7453 합이 0인 네 정수 Java 풀이

 

BOJ 7453번 합이 0인 네 정수

 

약간 독특한 문제다. 시간 제한도 12초로 비교적 길고, 입력도 다소 독특하게 주어진다.

문제는 간단한데, 단순하게 A, B, C, D 배열의 모든 조합을 차례대로 4중 반복문을 쓰게되면 시간복잡도는 4000^4(256조)로 눈 앞이 아득해진다. 

다른 방법을 찾아야 하는데, 단순히 정렬을 통해 다중 포인터를 쓰는 방법은 배열이 4개나 있기 때문에 쓰기 어렵다.

때문에 배열을 2개씩 묶어 각 합을 통해 새로운 리스트 2개를 만들어 주고, 정렬한 뒤 투 포인터를 사용해준다.
배열을 2개씩 묶으면 4000^2(1,600만)를 2번 수행하기 때문에 크지만, 나름 합리적으로 새로운 리스트를 만들어 줄 수 있겠다.
또, 새로 생성된 리스트는 길이가 최대 1,600만이 되고 정렬시 시간 복잡도는 O(N log N) 투 포인터로 돌아다녀도 시간 복잡도가 O(N)이기에 도전해볼만 하다. 

 

첫 번째 풀이 - 오답(시간 초과)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	static int a, b, c, d;
	static int[] A, B, C, D;
	static ArrayList<Integer> leftList, rightList;
	static int N, ans;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		B = new int[N];
		C = new int[N];
		D = new int[N];
		
		leftList = new ArrayList<>();
		rightList = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			StringTokenizer 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());
		}
		
		makeSum(A, B, leftList);
		makeSum(C, D, rightList);
		
		Collections.sort(leftList);
		Collections.sort(rightList);
		
		ans = 0;
		calcAns();
		
		System.out.println(ans);
		
	}
	private static void calcAns() {
		int left = 0;
		int right = rightList.size() - 1;
		
		while(left < leftList.size() && right >= 0) {
			int lv = leftList.get(left);
			int rv = rightList.get(right);
			
			if(lv + rv == 0) {
				int lc = 0;
				while(leftList.get(left) == lv) {
						lc++;
						left++;
				}
				
				int rc = 0;
				while(rightList.get(right) == rv) {
					rc++;
					right--;
				}
				ans += lc * rc;
			}
			else if(lv + rv < 0) left++;
			else if(lv + rv > 0) right--;
		}
		
	}
	
	private static void makeSum(int[] arr1, int[] arr2, ArrayList<Integer> list) {
		for(int i = 0; i < arr1.length; i++) {
			for(int j = 0; j < arr2.length; j++) {
				list.add(arr1[i]+arr2[j]);
			}
		}
	}

}

 

잘 구현한 것 같았는데, 시간 초과를 받았다. 틀렸으면 틀렸지 시간초과가 나는 것은 뭔가 잘못 접근했다는 느낌이 들어 게시판을 둘러보던 중 도움을 얻게 됐다.

글 제목: Java 시간 초과 나시는 분들 - https://www.acmicpc.net/board/view/50851

다 같은 N log N인줄 알았는데, 그게 아니었다. 아무래도 Non Primitive 자료형보다는 Primitive 자료형의 속도가 정렬에서 꽤나 크게  빠른 모양이다. 

앞에서 배열합을 구할때 이미 1,600만씩 두 번 => 약 3,200만, 정렬 과정에서 N log N으로 계산하면 3억 6,800인데 이를 2번 수행하므로 7억 7.600만, 투 포인터로 돌아다니며 다시 3,200만... 그리 크지는 않을 것 같지만 입출력에 자잘한 코드들의 수행시간까지 더하면 시간초과가 날 수도 있나.. 싶었다. (그래도 12초면 충분한 것 같은데....)

여하튼 위 코드에서 두 배열 원소의 합을 리스트로 저장하던 것(leftList, rightList)을 각각 Array로(leftArr, rightArr) 바꿔줬다. 
(leftArr, rightArr의 크기: int[N*N])

두 번째 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int[] A, B, C, D;
//	static ArrayList<Integer> leftList, rightList;
	static int[] leftArr, rightArr;
	static int N, ans;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		B = new int[N];
		C = new int[N];
		D = new int[N];
		
//		leftList = new ArrayList<>();
//		rightList = new ArrayList<>();
		leftArr = new int[N*N];
		rightArr = new int[N*N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer 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());
		}
		
//		makeSum(A, B, leftList);
//		makeSum(C, D, rightList);
		makeSum(A, B, leftArr);
		makeSum(C, D, rightArr);
		
//		Collections.sort(leftList);
//		Collections.sort(rightList);
		Arrays.sort(leftArr);
		Arrays.sort(rightArr);
		
		ans = 0;
		calcAns();
		
		System.out.println(ans);
		
	}
	// 두 배열에서 원소를 하나씩 뽑아 만들 수 있는 합의 모든 경우를 list에 담아줌
	private static void makeSum(int[] arr1, int[] arr2, int[] whereArr) {
		int index = 0;
		for(int i = 0; i < arr1.length; i++) {
			for(int j = 0; j < arr2.length; j++) {
				whereArr[index] = arr1[i] + arr2[j];
				index++;
			}
		}
	}
	

	
	private static void calcAns() {
		int left = 0;
		int right = rightArr.length - 1;
		while(left < leftArr.length && right >= 0) {
			int lv = leftArr[left];
			int rv = rightArr[right];
			
			if(lv + rv == 0) {
				int lc = 0;
				while(leftArr[left] == lv) {
						lc++;
						left++;
				}
				
				int rc = 0;
				while(rightArr[right] == rv) {
					rc++;
					right--;
				}
				ans += lc * rc;
			}
			else if(lv + rv < 0) left++;
			else if(lv + rv > 0) right--;
		}
	}
}

 

이제는 런타임에러(ArrayIndexOutOfBounds)를 받았다. 문제는 채점률이 기억상 50% 이상 올라간 상태에서 런타임에러가 나는 것이었다. 처음에는 리스트를 Array로 바꿔줬기 때문에 두 배열의 합을 저장하는 배열의 문제일 것이라 예상했으나, 그 문제가 아니었다.

이런 실수는 은근히 극적인 테스트케이스에서 많이 발생하는 것 같다.

n=1인 경우에 calcAns 함수 내 이중 while문의 조건에서 left나 right변수가 각 Arr의 범위를 벗어나는 문제였다. 그 때문에 그 부분만 아래와 같이 고쳐주고 제출했다.

private static void calcAns() {
	int left = 0;
	int right = rightArr.length - 1;
	while(left < leftArr.length && right >= 0) {
		int lv = leftArr[left];
		int rv = rightArr[right];
		
		if(lv + rv == 0) {
			int lc = 0;
			while(true) {
				// N = 1인 경우 outOfBounds를 피해주기 위한 예외처리
				if(left == leftArr.length) break;
				if(leftArr[left] == lv) {
					lc++;
					left++;
				}else {
					break;
				}
			}
			
			int rc = 0;
			while(true) {
				// N = 1인 경우 outOfBounds를 피해주기 위한 예외처리 
				if(right < 0) break;
				if(rightArr[right] == rv) {
					rc++;
					right--;
				}else {
					break;
				}
			}
			ans += lc * rc;
		}
		else if(lv + rv < 0) left++;
		else if(lv + rv > 0) right--;
	}
}

 

이번엔 7~80%대까지 채점률이 올라가다가 틀렸다는 결과를 받았다. 슬슬 머리가 아프고 포기해야 하는지 마음이 복잡할 때쯤, 문제점을 발견했다. 문제는 Integer type의 범위 제한이다. 

배열 네 개에서 각 하나씩 값을 더해도 각 정수의 절댓값이 2^28(약 2억)이고, 답을 나타내는 ans변수도 각 배열 원소의 합의 최대 길이가 1,600만이었기 때문에 모두 안전하다고 생각했다. 하지만, 투 포인터로 개수를 셀 때는 각 리스트(배열 원소의 합을 담은 배열)에서 같은 수의 개수만큼 세어 곱셈을 하게 된다. 결국 integer의 범위를 초과하기 때문에, 반드시 ans를 long 타입으로 선언하고, 계산할 때도 int를 long으로 바꿔 계산하고 저장시켜야 한다.

여기까지 수행하면, 정상적으로 AC를 받을 수 있다.

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int[] A, B, C, D;
	static int[] leftArr, rightArr;
	static int N;
	static long ans;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		B = new int[N];
		C = new int[N];
		D = new int[N];
		
		leftArr = new int[N*N];
		rightArr = new int[N*N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer 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());
		}
		

		makeSum(A, B, leftArr);
		makeSum(C, D, rightArr);
		
		Arrays.sort(leftArr);
		Arrays.sort(rightArr);
		
		ans = 0;
		calcAns();
		
		System.out.println(ans);
		
	}
	// 두 배열에서 원소를 하나씩 뽑아 만들 수 있는 합의 모든 경우를 list에 담아줌
	private static void makeSum(int[] arr1, int[] arr2, int[] whereArr) {
		int index = 0;
		for(int i = 0; i < arr1.length; i++) {
			for(int j = 0; j < arr2.length; j++) {
				whereArr[index] = arr1[i] + arr2[j];
				index++;
			}
		}
	}
	
	private static void calcAns() {
		int left = 0;
		int right = rightArr.length - 1;
		while(left < leftArr.length && right >= 0) {
			int lv = leftArr[left];
			int rv = rightArr[right];
			
			if(lv + rv == 0) {
				int lc = 0;
				while(true) {
					// N = 1인 경우 outOfBounds를 피해주기 위한 예외처리
					if(left == leftArr.length) break;
					if(leftArr[left] == lv) {
						lc++;
						left++;
					}else {
						break;
					}
				}
				
				int rc = 0;
				while(true) {
					// N = 1인 경우 outOfBounds를 피해주기 위한 예외처리 
					if(right < 0) break;
					if(rightArr[right] == rv) {
						rc++;
						right--;
					}else {
						break;
					}
				}
				ans += (long)lc * (long)rc;
			}
			else if(lv + rv < 0) left++;
			else if(lv + rv > 0) right--;
		}
	}
}