문제 이해하기
서로 다른 양의 정수로만 구성된 배열 nums가 주어집니다. 이때 a × b = c × d를 만족하는 튜플 (a, b, c, d)의 개수를 구하는 것이 목표입니다. 여기서 a, b, c, d는 모두 nums의 원소여야 하며, 네 값은 서로 달라야 합니다.
예를 들어 입력이 nums = [2, 3, 4, 6]이라면 정답은 8입니다. 실제로 만들 수 있는 튜플은 다음과 같습니다.
(2, 6, 3, 4), (2, 6, 4, 3), (6, 2, 3, 4), (6, 2, 4, 3), (3, 4, 2, 6), (4, 3, 2, 6), (3, 4, 6, 2), (4, 3, 6, 2)
이 튜플들은 모두 2 × 6 = 12와 3 × 4 = 12라는 동일한 곱을 활용한 것임을 알 수 있습니다.
접근 방법
핵심 아이디어는 "같은 곱을 만들어내는 숫자쌍이 몇 개인가"를 세는 것입니다. 해시 맵(defaultdict)을 사용하면 효율적으로 처리할 수 있습니다.
- 곱의 빈도를 저장할 딕셔너리 dic을 준비합니다. 존재하지 않는 키의 기본값은 0입니다.
- 정답을 저장할 변수 ans를 0으로 초기화합니다.
- i < j인 모든 인덱스 쌍에 대해 곱 nums[i] × nums[j]의 빈도를 dic에 1씩 증가시키며 기록합니다.
- dic의 각 빈도 값 v에 대해 다음을 검사합니다.
- v가 1이면 해당 곱으로는 두 쌍을 만들 수 없으므로 다음 항목으로 건너뜁니다.
- 그 외의 경우 v에서 1을 뺀 뒤, s = (v / 2) × (8 + 8 × v)를 계산하여 ans에 더합니다.
- ans를 정수로 변환하여 반환합니다.
왜 8을 곱할까?
같은 곱을 만드는 서로 다른 두 쌍을 하나 선택하면, 각 쌍 내부에서 두 숫자의 순서를 바꿀 수 있고(각각 2가지), 두 쌍 자체의 순서도 바꿀 수 있어(2가지) 총 2 × 2 × 2 = 8개의 튜플이 만들어집니다. 따라서 어떤 곱이 v번 등장했다면, 가능한 쌍의 조합 수 C(v, 2)에 8을 곱한 값이 그 곱이 기여하는 튜플의 개수입니다.
구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
def solve(nums):
dic = defaultdict(int)
ans = 0
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
dic[nums[i]*nums[j]] += 1
for v in dic.values():
if v == 1:
continue
v = v - 1
s = (v/2) * (8 + 8*v)
ans += s
return int(ans)
nums = [3, 4, 6, 2]
print(solve(nums))
입력
[3, 4, 6, 2]
출력
8
[3, 4, 6, 2]에서는 3 × 4 = 12와 6 × 2 = 12로 같은 곱을 만드는 쌍이 정확히 한 세트 존재하므로 결과는 8이 됩니다.
복잡도 분석
모든 쌍의 곱을 한 번씩 계산하므로 시간 복잡도는 O(n²)입니다. 최악의 경우 모든 쌍의 곱이 서로 달라 딕셔너리에 n(n-1)/2개의 키가 저장될 수 있으므로 공간 복잡도 역시 O(n²)입니다.