파이썬으로 풀어보는 4Sum II: 합이 0이 되는 네 수의 조합 찾기

문제 이해하기

정수 값으로 이루어진 네 개의 리스트 A, B, C, D가 주어졌다고 가정해 봅시다. 이때 A[i] + B[j] + C[k] + D[l]의 결과가 0이 되는 튜플 (i, j, k, l)의 개수를 구하는 것이 이번 문제의 목표입니다.

모든 리스트는 동일한 길이 N을 가지며, N은 0 이상 500 이하입니다. 또한 각 정수는 -2²⁸부터 2²⁸ - 1 사이의 범위에 있고, 결과값은 최대 2³¹ - 1을 넘지 않는다고 보장됩니다.

입력 예시

예를 들어 입력이 다음과 같다면,

[1,2]
[-2,-1]
[-1,2]
[0,2]

출력은 2가 됩니다. 조건을 만족하는 튜플이 정확히 두 개 존재하기 때문입니다.

(0, 0, 0, 1): A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0): A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

접근 방법: 해시맵 활용하기

네 개의 리스트를 전부 하나씩 탐색하는 완전 탐색(Brute Force)은 O(N⁴)의 시간이 걸립니다. N = 500이라면 약 600억 번에 가까운 연산이 필요해 비효율적입니다. 대신 문제를 두 그룹으로 나누고 해시맵(딕셔너리)을 활용하면 시간 복잡도를 O(N²)까지 크게 줄일 수 있습니다.

구체적인 절차는 다음과 같습니다.

sums라는 이름의 딕셔너리(맵)를 생성합니다.
리스트 A와 B의 모든 조합에 대해 두 원소의 합 i + j가 몇 번 등장하는지 sums에 기록합니다.
- i + j가 아직 맵에 없다면 sums[i + j] = 1로 설정합니다.
- 이미 존재한다면 해당 값을 1 증가시킵니다.
정답 카운터를 0으로 초기화합니다.
리스트 C와 D의 모든 조합에 대해 -(i + j)가 sums에 존재하는지 확인하고, 존재한다면 카운터에 sums[-(i + j)]를 더합니다.
카운터 값을 반환합니다.

여기서 핵심 아이디어는 A[i] + B[j] = -(C[k] + D[l])이라는 관계식입니다. A와 B의 쌍 합을 미리 저장해 두면, C와 D의 쌍 합에 대해 '더했을 때 0이 되는 값'이 몇 개 있는지 한 번의 조회(O(1))로 바로 알 수 있습니다.

파이썬 구현 코드

아래 코드를 통해 실제 구현 과정을 살펴보겠습니다.

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        sums = {}
        for i in A:
            for j in B:
                if i+j not in sums:
                    sums[i+j] = 1
                else:
                    sums[i+j] += 1

        counter = 0
        for i in C:
            for j in D:
                if -1 * (i+j) in sums:
                    counter += sums[-1*(i+j)]
        return counter

ob1 = Solution()
print(ob1.fourSumCount([1,2], [-2,-1], [-1,2], [0,2]))

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻습니다.

복잡도 분석

시간 복잡도: O(N²) — A×B 조합의 합을 기록하는 단계와 C×D 조합을 확인하는 단계에 각각 O(N²)이 소요됩니다.
공간 복잡도: O(N²) — 최악의 경우 A와 B의 쌍 합 종류가 N²개만큼 딕셔너리에 저장될 수 있습니다.