[LeetCode] 454. 4Sum II [Python] 해시테이블

leetcode.com/problems/4sum-ii/

4Sum II - LeetCode

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B [j] + C [k] + D [l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

 

이 문제는 합이 0인 네 정수의 조합이 몇 개인지 찾는 문제입니다. 백준의 7453 합이 0인 네 정수와 같은 문제입니다. 

 

 

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

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

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

 

 

 

저는 문제를 풀 때, 바로 옵티멀 한 답을 찾기보단 가장 기본적인 방법을 생각하고, 그 후에 퍼포먼스를 개선하는 편이기 때문에, 이번 문제를 보고 brute force 방법인 4개의 for loop을 사용하는 것을 생각했습니다.

---

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    	ans = 0
        for a in A:
            for b in B:
            	for c in C:
            	    for d in D:
            	        if a+b+c+d == 0:
            	            ans += 1
        return ans

---

하지만, 4개의 반복문을 사용할 경우 시간 복잡도가 O(n^4)으로 사악한 퍼포먼스가 나오기 때문에, 배열의 길이가 조금이라도 길어진다면 결과를 보는데 세월아 네월아 기다려야 합니다. 따라서 optimzation은 필수! 제가 brutal 한 방법을 늘 먼저 생각하는 이유는, 프로그램의 런타임을 해결할 때 어떤 식으로 접근을 해야 할지 아이디어를 주기 때문인데요, 저 4개의 for loop을 보시면서 혹시 '이미 계산된 값을 중복해서 계속 계산한다'라는 생각 안 드시나요? 예를 들어, 마지막 for loop을 보시면 a+b+c값은 고정되어있고 d값만 계속 바꿔줍니다. 또 c와 연관된 for loop을 생각해보자면 a+b값은 고정된 채로 c+d값만 매번 새로운 값이 나옵니다. 하지만 저 반복문 안의 반복문 안의 반복문 안의 반복문 때문에 이미 계산된 값을 계속 반복해서 계산하게 되는 거죠.

 

그렇다면, 저 중복되는 부분을 없애면 런타임 개선에 큰 도움이 되지 않을까요?

---

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        lut = {}
        for i in A:
            for j in B:
                if i + j in lut:
                    lut[i + j] += 1
                else:
                    lut[i + j] = 1
        
        ans = 0
        for i in C:
            for j in D:
                if (-i - j) in lut:
                    ans += lut[-j-i]
        return ans

---

위의 솔루션은 dictionary를 이용한, 즉 맵을 이용한 방법입니다. 모든 A+B를 계산하는 반복문 하나와, 모든 C+B를 계산하는 반복문을 이용하여 rum time O(n^2)이 나오는 답입니다. 문제에서 요구하는 것이 A+B+C+D=0이 되는 조합을 찾는 것이므로, A+B = -C-D의 조합을 찾는 방법으로 접근을 했습니다.

 

먼저 A와 B가 만들어낼 수 있는 모든 쌍의 합을 계산한 결과값이 key로 사용되고, 그 key에 따른 value는 얼마나 많은 pair가 그 합을 만들어 낼 수 있는지에 대한 number of pairs입니다. 그렇게 모든 A와 B의 합과 그 합을 만들 수 있는 쌍의 개수를 map에 저장을 합니다. 그리고 C와 D가 만들어낼 수 있는 모든 합을 앞선 방법과 같이 계산합니다. 단, 이때는 C+D의 sum을 dictionary에 저장하는 것이 아니라 -(C+D) 값이 맵에 있는지를 확인합니다. 만약 그 값이 존재한다면, A+B = -(C+D)이므로 A+B+C+D = 0이 성립이 됩니다. 따라서, -C-D가 맵의 key로 저장되어있는 value를 더하면 A+B+C+D=0이 되는 모든 조합을 찾을 수 있습니다. 해당 솔루션의 Complexity를 계산하면, run time O(n^2) space O(n)이 나옵니다. 앞선 brute force 방법에 비하면 런타임이 상당히 개선됨을 확인할 수 있습니다.