백준 7453 (합이 0인 네 정수)

문제

---

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

 

풀이

---

conpulake.tistory.com/90

백준 2632 (피자판매)

위의 문제에서 두개로 나누어져 있는 피자를 선택하는 방법을 통해 풀어본 경험이 있어서 문제의 접근은 어렵지않았다.

 

A, B, C, D 네개의 배열의 모든 경우의 수를 만들면 n^4 다.

하나의 배열의 n 의 최댓값이 4000을 감안하면 4000^4 의 시간 복잡도가 발생하기 때문에 효율이 정말 안좋다.

 

그래서 생각한게 A, B 배열의합, C, D배열의 합을 미리 구한뒤 두개의 포인터를 맨앞과 맨뒤에서 차례대로 더해가는 것.

이렇게하면 O(n^2) 에서 얼마 차이 나지않을것으로 판단하여 시간복잡도가 크게 나지 않을 것 같았다.

 

문제를 푸는 알고리즘은 맞았지만, 처음 DFS를 통해 해당 값을 List에 넣고 풀었더니 시간초과가 나왔다.

<List 사용 시간초과 코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	static long[][] num;
	static int n;
	static List<Long> list1, list2;
	static long answer = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(bufferedReader.readLine());
		num = new long[4][n];
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			for(int j = 0 ; j < 4 ; j++) {
				num[j][i] = Long.parseLong(st.nextToken());
			}
		}
		
		list1 = new ArrayList<Long>();
		list2 = new ArrayList<Long>();
		for(int i = 0 ; i < n ; i++) {
			dfs(1, num[0][i], 1, list1);
			dfs(3, num[2][i], 1, list2);
		}
		
		Collections.sort(list1);
		Collections.sort(list2);
		
		int left = 0, right = list2.size() -1;
		
		while(left < list1.size() && right >= 0) {
			long leftSum = list1.get(left);
			long rightSum = list2.get(right);
			
			if(leftSum + rightSum == 0) {
				long leftCount = 0;
				long rightCount = 0;
				
				while(left < list1.size() && list1.get(left) == leftSum) {
					leftCount++;
					left++;
				}
				
				while(right >= 0 && list2.get(right) == rightSum) {
					rightCount++;
					right--;
				}
				
				answer += leftCount * rightCount;
			}
			
			if(leftSum + rightSum < 0) {
				left++;
			}
			
			if(leftSum + rightSum > 0) {
				right--;
			}
		}
		
		System.out.println(answer);
	}
	
	static void dfs(int alph, long sum, int count, List<Long> list) {
		
		if(count == 2) {
			list.add(sum);
			return;
		}
		
		for(int i = 0 ; i < n ; i++) {
			dfs(alph + 1, sum + num[alph][i], count + 1, list);
		}
	}
}

예상 List의 특성상 배열에서는 값을 꺼내오는 것이 편하지만 List는 get을하여 찾는 방식이 배열보다 느려서 일것 같다.

 

그래서 배열을 사용해서 풀면 같은 알고리즘이지만 정답이 된다.

 

<정답 전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	static long[][] num;
	static int n;
	static long[] AB, CD;
	static long answer = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(bufferedReader.readLine());
		num = new long[4][n];
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			for(int j = 0 ; j < 4 ; j++) {
				num[j][i] = Long.parseLong(st.nextToken());
			}
		}
		
		AB = new long[ n * n ];
		CD = new long[ n * n ];
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				AB[n * i + j] = num[0][i] + num[1][j];
				CD[n * i + j] = num[2][i] + num[3][j];
			}
		}
		
		Arrays.sort(AB);
		Arrays.sort(CD);
		
		int left = 0, right = CD.length - 1;
		
		while(left < AB.length && right >= 0) {
			long leftSum = AB[left];
			long rightSum = CD[right];
			
			if(leftSum + rightSum == 0) {
				long leftCount = 0;
				long rightCount = 0;
				
				while(left < AB.length && AB[left] == leftSum) {
					leftCount++;
					left++;
				}
				
				while(right >= 0 && CD[right] == rightSum) {
					rightCount++;
					right--;
				}
				
				answer += leftCount * rightCount;
			}
			
			if(leftSum + rightSum < 0) {
				left++;
			}
			
			if(leftSum + rightSum > 0) {
				right--;
			}
		}
		
		System.out.println(answer);
	}
}

 

List 보다 배열을 사용할 경우가 시간효율이 더 좋게 나온다는 것을 알게되었다.