[LeetCode] 1726. Tuple with Same Product (Python)

Problem

 

Solution

permutation

순열과 조합을 사용하여 푸는 문제.

defaultdict 의 value를 리스트로 선언하여 2개의 integer 곱을 key로, tuple 을 value로 저장하였다.

value 길이 (리스트)가 2 이상이면 value 길이만큼 8 x nC2 를 곱하여 경우의 수를 구하고 정답에 ++ 하였다.

8을 곱하는 이유는 a*b = c*d 인 (a,b,c,d)의 경우의 수가 8이기 때문! ( 4permutation * 2 pairs)

nC2를 한 이유는 value 길이 = n 에서 2개의 튜플을 선택해야되기 때문!

 

Code

from collections import defaultdict

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        def factorial(x):
            res = 1
            for i in range(2, x+1):
                res = res * i
            return res
        
        def combination(n, r):
            return factorial(n) // (factorial(r) * factorial(n-r))
            
        map = defaultdict(list)

        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                multiple = nums[i] * nums[j]
                map[multiple].append((nums[i], nums[j]))
        
        cnt = 0
        for k, v in map.items():
            if len(v) >= 2:
                cnt += 8 * combination(len(v), 2)
    
        return cnt

 

Complexity

Time Complexity

• 2중 for문을 순회하므로 O(n^2)

 

Space Complexity

 

• map은 최대 O(N²) 크기의 리스트를 가질 수 있음.
• 최악의 경우, 모든 숫자의 곱이 다 다르면 map의 크기는 O(N²).
• 모든 숫자의 곱이 같은 경우 map에 O(N²)개의 값이 저장될 수 있음.

 

다른 풀이

• value에 굳이 튜플을 저장하지 않고 중복된 값 개수만 n++
• nC2 * 8 을 해준다. 이때 n=1이면 스킵.
• combination은 math.comb 메서드 사용
• 시간복잡도: O(N^2)
• 공간복잡도: O(N^2) -> dictionary 사용

def tupleSameProduct(self, nums: List[int]) -> int:
        counts = defaultdict(int)
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                counts[nums[i] * nums[j]] += 1

        ans = 0

        for v in counts:
            count = counts[v]
            if count > 1:
                ans += count * (count - 1) // 2 * 8  # 조합 계산 최적화 (math.comb 대신 사용)
                또는
            	ans += math.comb(count, 2) * 8
        
        return ans