네 개의 숫자 리스트 A, B, C, D와 하나의 목표값(target)이 주어졌다고 가정해 봅시다. 이때 A[i] + B[j] + C[k] + D[l]의 합이 목표값과 같아지는 서로 다른 사중조(quadruple) (i, j, k, l)의 개수를 구하는 것이 문제입니다.
예를 들어 입력이 다음과 같다면,
- A = [5, 4, 3]
- B = [8, 4]
- C = [6, 2]
- D = [4, 10]
- target = 23
출력은 3이 됩니다. 조건을 만족하는 조합은 [5, 8, 6, 4], [3, 4, 6, 10], [3, 8, 2, 10] 세 가지이기 때문입니다.
문제 해결 접근 방식
단순하게 네 개의 리스트를 모두 탐색하면 O(n⁴)의 시간 복잡도가 발생합니다. 대신 해시 맵(hash map)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 A와 B에서 나올 수 있는 모든 두 수의 합을 계산하여 맵(m)에 저장하고, 각 합이 등장한 횟수를 기록합니다.
- 그다음 C와 D에서 나오는 모든 두 수의 합(k + z)에 대해, 목표값에서 그 합을 뺀 값(target - (k + z))이 맵에 존재하는지 확인합니다.
- 존재한다면, 해당 값의 등장 횟수만큼 정답 카운트(count)에 더해줍니다.
이 방식을 단계별로 정리하면 다음과 같습니다.
- count := 0 으로 초기화
- m := 빈 맵 생성
- A의 각 원소 i에 대해:
- B의 각 원소 j에 대해 m[i + j] 값을 1씩 증가
- C의 각 원소 k에 대해:
- D의 각 원소 z에 대해:
- (target - (k + z))가 m에 존재하면 count += m[target - (k + z)]
- D의 각 원소 z에 대해:
- count 반환
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution: def solve(self, A, B, C, D, target): count = 0 from collections import defaultdict from collections import Counter m = defaultdict(int) for i in A: for j in B: m[i + j] += 1 for k in C: for z in D: if target - (k + z) in m: count += m[target - (k + z)] return count ob = Solution() A = [5, 4, 3] B = [8, 4] C = [6, 2] D = [4, 10] target = 23 print(ob.solve(A, B, C, D, target))
입력
[5, 4, 3], [8, 4], [6, 2], [4, 10], 23
출력
3
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n²)입니다. A와 B의 모든 조합을 한 번 순회하고(O(n²)), C와 D의 모든 조합도 한 번 순회하기 때문입니다(O(n²)). 공간 복잡도 역시 A와 B의 합을 저장하는 맵 때문에 최악의 경우 O(n²)입니다. 완전 탐색의 O(n⁴)보다 훨씬 효율적이며, 이는 '4Sum II' 유형의 문제에서 널리 사용되는 표준적인 최적화 기법입니다.