[Python] 1726. Tuple with Same Product

난이도 : medium

 

a * b = c * d일 때의 tuple (a,b,c,d)의 갯수를 return하는 문제.

 

a * b = c * d = m인 쌍의 갯수 n을 알아내고, m마다 nP2(= n * n - 1)을 취한 뒤 sum

조합에서 a, b와 c, d 각각 위치를 바꿀 수 있고, (a, b)쌍과 (c, d)쌍의 위치도 바꿀 수 있기 때문에, 그 경우의 수를 고려하면 sum 값에 4를 곱해야 한다.

from collections import Counter
class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [nums[i]* nums[j] for i in range(n) for j in range(i+1,n)]
        count = Counter(arr)
        a = Counter([cnt for x, cnt in count.items() if cnt >= 2])
        return sum([4 * i * (i-1) * j for i, j in a.items()])

1. nums의 다른 요소들끼리 곱한 리스트 arr를 제작
2. arr를 Counter 진행하면, 리스트 arr 내의 요소가 몇 개 있는지 count된다.
3. count의 값은 주로 {m : n}와 같은 형식인데, 이 문제에서는 쌍의 갯수인 n만 알아내면 되기 때문에, m의 값이 2개 이상인 경우를 또 Counter 진행했다. m의 값이 2개 이상인 이유는, tuple 1개를 만드려면 최소 2개의 쌍이 필요하기 때문
4. a의 값은 {n, j} 형식인데, 쌍의 갯수인 n인 경우가 j개라는 의미다. 쌍의 갯수가 n이면 nP2(n * n-1)을 취한 뒤, j를 곱하고, 조합 위치의 경우의 수인 4를 또 곱해준 값을 sum하면 끝

Runtime : 279ms (97.16%)

Memory :57.60MB (10.43%)