문제 링크](https://www.acmicpc.net/problem/7453)

성능 요약

메모리: 161996 KB, 시간: 4392 ms

분류

이분 탐색, 중간에서 만나기, 정렬, 두 포인터

제출 일자

2025년 1월 21일 15:51:39

문제 설명

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

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

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

풀이

느낀점

• HashMap은 요소의 포함여부를 찾는데 O(1)이라서 가장 빠를줄 알았는데, 어림도 없이 시간초과가 나서 당황스러웠다. 풀이를 참고하려고 찾아보다가 Map의 느린 연산으로는 이 문제가 풀리지 않는다고 하는 것 같다.
  • 참고한 글
• HashMap으로 푼 후에 알고리즘 분류를 보니 해시는 있지도 않았고, 이분탐색과 투포인터, 중간에서 만나기가 있었다.
• 중간에서 만나기(Meet in the middle) 알고리즘은 완전탐색을 해야 하는데 그 수가 너무 클때 사용한다고 한다. 예를 들어 주어진 배열을 동일한 크기의 두 배열로 나누어 경우의 수를 생각해보는 것이다.
  • 참고한 글
• 처음 들어보는 알고리즘 기법인데, 원리자체는 원래 풀려고 했던 방식과 비슷했다.

설계 : 30분

• A, B, C, D 네개의 배열을 각각 A+B 경우를 모두 담은 배열, C+D 경우를 모두 담은 배열 2개로 줄인다. O(NN) + O(NN)
• 처음에는 배열이 아닌 Map에 <합, 개수>를 담아 동일한 경우의 수를 저장하고 간단히 뽑아보려 했지만, 시간초과가 났다.
• AB, CD 두 배열을 투포인터로 순회하며 두 요소의 값이 0인 경우를 카운트 했다. O(N^2)
  • 원래는 Map으로 구성된 AB의 key를 순회하며 S-AB 가 CD Map에 존재하는지 확인하고 경우의 수를 value에서 뽑아 계산하려고 했다. O(N^2)이지만 map의 연산이 좀 느린 것 같다..
  • 또 다른 방법으로는 S-AB가 CD에 존재하는이 이분탐색으로 찾는 방법이 있다. (투포인터보다는 오래 걸린다) O(N^2logN)

코드(Java)

• 구현 시간: 40분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 합이 0인 네 정수_7453
 * Date: 2025.01.21
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		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++) {
			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());
		}

		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] = A[i] + B[j];
				CD[idx++] = C[i] + D[j];
			}
		}
		Arrays.sort(AB);
		Arrays.sort(CD);

		long answer = 0;
		int abIdx = 0;
		int cdIdx = n*n - 1;
		while (abIdx < n*n && cdIdx >= 0) {
			int gap = AB[abIdx] + CD[cdIdx];
			if (gap > 0) cdIdx--;
			else if (gap < 0) abIdx++;
			else {
				long abCnt = 0;
				long cdCnt = 0;
				int ab = AB[abIdx];
				int cd = CD[cdIdx];
				while (abIdx < n*n && AB[abIdx] == ab) {
					abCnt++;
					abIdx++;
				}
				while (cdIdx >= 0 && CD[cdIdx] == cd) {
					cdCnt++;
					cdIdx--;
				}

				answer += abCnt * cdCnt;
			}
		}

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