[Baekjoon] 7453 - 합이 0인 네 정수 (C#)

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

7453번: 합이 0인 네 정수

단순히 모든 경우의 수를 고려해서 풀어도 문제는 없으나 $O(n^4)$ 시간 복잡도가 나오게 되고, 입력으로 들어오는 데이터의 크기 또한 최대 4,000개가 들어올 수 있기 때문에 시간 초과가 나오게 됩니다. 따라서 단순히 풀 수는 없고 최적화가 필요한 문제라고 볼 수 있습니다.

 

일단 문제를 보면 A + B + C + D = 0을 만족하는 모든 경우의 수를 찾아야 합니다. 하지만 무작정 모든 경우의 수를 확인할 수는 없기 때문에 먼저 A + B와 C + D로 나눠서 접근해 보았습니다. A + B와 C + D의 모든 경우의 수를 구해서 따로 저장해두면 4개의 배열에서 2개의 배열을 비교하는 문제가 됩니다. 새롭게 만들어진 2개의 배열을 다시 비교해서 둘을 더했을 때 0이 나오는 경우를 찾아주면 되는 것이죠.

 

하지만 문제는 이 2개의 배열을 비교하는 부분입니다. 단순히 2중 반복문을 사용해서 비교를 하게 되면 시간 복잡도가 다시 $O(n^4)$이 되어 의미가 없어집니다. 그렇기에 정렬과 이진 탐색(binary search)을 사용해서 풀어야 하는데 저는 좀 다른 방법으로 해시 테이블(hash table)을 이용해 보았습니다. 해시 테이블은 검색, 삽입, 삭제의 시간 복잡도가 모두 $O(1)$로 상수 시간이기 때문에 충돌이 없다는 가정하에 $O(n^2)$으로 통과할 수 있습니다.

 

전체적인 알고리즘은 다음과 같습니다.

1. A + B, C + D 결과를 따로 계산해서 키는 연산 결과, 값은 그 수의 개수로 각각 해시 테이블에 저장
2. A + B 해시 테이블에서 키를 하나씩 꺼내서 음수를 취한 뒤, C + D 해시 테이블에 그 값이 있는지 확인 (예를 들어 A + B 해시 테이블에서 30을 꺼낸 뒤 -30으로 바꾸고 C + D에 -30이 있나 확인)
3. 만약 존재한다면 해당 키에 대응되는 값(그 키의 개수)을 서로 곱한 뒤 개수를 셈 (예를 들어 A + B 해시 테이블에 30이 3개, C + D 해시 테이블이 -30이 5개가 있는 경우 0이 되는 경우의 수는 모두 15개가 있으므로 이 둘을 곱한 15를 셈)
4. 위 2 ~ 3 과정을 계속 반복해서 합이 0인 모든 경우의 수를 구하고 출력

주의할 점이 있다면 정답이 int 범위를 벗어날 수 있기 때문에 적절한 자료형을 사용하셔야 합니다. 처음에는 C++ STL의 unordered_map을 이용해서 구현했는데 오버헤드가 심해서 그런지 시간 초과를 받았습니다. C#의 Dictionary를 사용했더니 바로 통과가 되더군요. 아무래도 해시 테이블로 짜실 분들은 직접 구현하는 것이 더 좋을 것 같습니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        ulong answer = 0;

        int[] arrA = new int[n];
        int[] arrB = new int[n];
        int[] arrC = new int[n];
        int[] arrD = new int[n];

        // 배열 데이터 입력
        for (int i = 0; i < n; i++)
        {
            string[] strArr;
            strArr = Console.ReadLine().Split();

            arrA[i] = int.Parse(strArr[0]);
            arrB[i] = int.Parse(strArr[1]);
            arrC[i] = int.Parse(strArr[2]);
            arrD[i] = int.Parse(strArr[3]);
        }

        Dictionary<int, ulong> dictAB = new Dictionary<int, ulong>();
        Dictionary<int, ulong> dictCD = new Dictionary<int, ulong>();

        // A + B, C + D 결과의 개수를 계산해서 따로 보관
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int resultAB = arrA[i] + arrB[j];
                int resultCD = arrC[i] + arrD[j];

                if (dictAB.ContainsKey(resultAB))
                {
                    dictAB[resultAB]++;
                }
                else
                {
                    dictAB.Add(resultAB, 1);
                }

                if (dictCD.ContainsKey(resultCD))
                {
                    dictCD[resultCD]++;
                }
                else
                {
                    dictCD.Add(resultCD, 1);
                }
            }
        }

        // (A + B) == (C + D) 경우를 모두 찾고 개수를 계산
        foreach (int resultAB in dictAB.Keys)
        {
            // (C + D) 리스트에 -(A + B) 값이 존재하는지 확인
            if (dictCD.ContainsKey(-resultAB))
            {
                answer += dictAB[resultAB] * dictCD[-resultAB];
            }
        }

        Console.WriteLine(answer);
    }
}