백준 7453 : 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

[ 문제풀이 ]

N이 최대 4000이기 때문에 모든 경우를 구한다면 N^4으로 시간 초과가 발생하게 된다.

그렇다면 시간 복잡도를 낮춰야 하는데 이런 유형의 문제를 풀어봤다면 투포인터나 이분 탐색으로 해결할 수 있다는 것을 알 수 있다.

A, B와 C, D를 나눠서 각각 모든 데이터의 합을 만들어서 저장한 후, AB 합 데이터를 돌면서 CD 합 데이터에서 lowerBound와 upperBound를 활용해서 개수를 구해주면 된다.

주의해야 할 점은 lowerBound, upperBound를 사용하기 위해 합 데이터를 정렬해줘야 하는데 ArrayList가 아닌 int[]로 데이터를 저장하여 정렬해줘야 한다.

ArrayList는 Colletions.sort, int[]는 Arrays.sort를 사용하는데 두 방식에서 시간 차이가 발생한다.

Collections.sort는 primitive type의 경우 dual pivot quicksort가 수행, non primitive type의 경우 merge sort가 수행된다고 한다.

근데 의문점은 나의 코드에서 CD 배열에서 이분 탐색을 수행하기 때문에 AB 배열은 정렬할 필요가 없는데 AB 배열을 정렬하면 통과가 되고 정렬하지 않으면 시간 초과가 발생한다. 이 부분은 이해가 안 간다.

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

public class Main {
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int n = Integer.parseInt(br.readLine());
			int[][] data = new int[n][4];
			for (int i = 0; i < n; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 4; ++j) {
					data[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			int[] AB = new int[n * n];
			int[] CD = new int[n * n];
			int idx = 0;
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					AB[idx] = data[i][0] + data[j][1];
					CD[idx++] = data[i][2] + data[j][3];
				}
			}
            
			Arrays.sort(AB); //AB는 정렬할 필요 없는데 생략하면 TLE 발생???
			Arrays.sort(CD);
            
			long answer = 0;
			for (int ab : AB) {
				int lower = lowerBound(-ab, 0, CD.length, CD);
				int upper = upperBound(-ab, 0, CD.length, CD);
				answer += upper - lower;
			}
			bw.write(answer + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int lowerBound(int key, int l, int r, int[] CD) {
		while (l < r) {
			int m = (l + r) >> 1;
			if (CD[m] < key) l = m + 1;
			else r = m;
		}
		return r;
	}
	
	public static int upperBound(int key, int l, int r, int[] CD) {
		while (l < r) {
			int m = (l + r) >> 1;
			if (CD[m] <= key) l = m + 1;
			else r = m;
		}
		return r;
	}

}