BOJ - 7453 합이 0인 네 정수

7453 합이 0인 네 정수 : https://www.acmicpc.net/problem/7453

---

Problem

---

Solve

4중 for문으로 모든 값을 비교해서 합이 0인 쌍의 개수를 구할수 있지만, N이 4000이므로 O(4000^4)로 절대 불가능하다.

최소 O(4000^2)로 줄여서 각 쌍을 구해야한다.

네 정수의 합의 결과값을 찾는 것이므로 A[i]과 B[i]의 합의 배열, C[i]과 D[i]의 합의 배열을 구해서 두 배열을 투 포인터로 비교하면 두개 배열의 합을 구하는 시간 O(2*N^2), 만들어진 두 배열을 투포인터로 비교하는 시간 ((N^2)+(N^2)) = O(N^2) + O(N^2) 즉, O(N^2)으로 문제를 해결할 수 있다.

---

Code

public class 합이0인네정수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		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++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			A[i] = a;
			B[i] = b;
			C[i] = c;
			D[i] = d;
		}

		//A와 B의 합 배열
		int[] AB = new int[N * N];
        //C와 D의 합 배열
		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] = A[i] + B[j];
				CD[idx] = C[i] + D[j];
				idx++;
			}
		}

		Arrays.sort(AB);
		Arrays.sort(CD);

		long answer = 0;

		int start = 0;
		int end = CD.length - 1;

		while(start<AB.length && end>=0){
			long sum = AB[start] + CD[end];

			//두 수의 합이 0이라면 정렬 되어 있는 배열이라 다음 원소와의 합도 0이 될수 있으므로
            //각각 AB배열과 CD배열이 연속으로 합이 0이 되는 배열을 찾아 이동시켜준다.
			if(sum==0){
				int startCount=0;
				int startIdx=start;
				while(start<AB.length && AB[start] == AB[startIdx]){
					startCount++;
					start++;
				}

				int endCount=0;
				int endIdx = end;
				while(end>=0 && CD[end] == CD[endIdx]){
					endCount++;
					end--;
				}

				answer += (long)startCount*(long)endCount;
			}else{
            	//두 배열 값의 합이 음수라면 두 값의 합이 0이 가까워져야하므로 AB배열의 값을 높여준다.
				if(sum < 0){
					start++;
				}
                //양수라면 CD배열의 값을 내려준다.
                else{
					end--;
				}
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference