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

 

난이도: Medium

문제 설명

---

 

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

 

문제 예제

---

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(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)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

 

제한 사항

---

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• All elements in nums are distinct.

 

✏️ Solution(솔루션)

---

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

        for i in range(n):
            for j in range(i+1, n):
                mul_value[nums[i]*nums[j]]+=1
        
        answer = 0
        for v in mul_value.values():
            if v >= 2:
                for i in range(v):
                    answer += 8 * i
        return answer

 

일단 각 페어를 곱한 값의 수를 세고, 딕셔너리를 만들어 이를 저장했다.

(ex) num[i] = 2, num[j] = 3 ==> mul_value[6] += 1)

 

이 때, 각 값에 따라 센 수가 2 이상이어야지 문제의 조건을 만족한다.

 

따라서 mul_value.values()의 요소가 2이상일 때만 answer에 값을 더해주어야한다.

 

어떤 값을 answer에 더해주어야할 지 몰라 이것저것 써보다가 다음과 같은 발견을 했다.

 

pair가 2개라면 8개이고, 3개이면 24개, 4개이면 48개였다.

 

이를 다른 식으로 써보면 다음과 같았다.

 

따라서 다음과 같이 코드를 작성하고 마지막에 answer를 return하여 정답을 맞출 수 있었다.

answer = 0
for v in mul_value.values():
   if v >= 2:
      for i in range(v):
         answer += 8 * i
return answer

 

다 풀고나서 생각났는데 굳이 위 코드처럼 하지 않고 answer += 8 * ((v*(v-1))//2) 수식을 사용하면 쉽게 구할 수 있다....

---

문제: 1726. Tuple with Same Product

 

깃허브: github

algorithmPractice/LeetCode/1364-tuple-with-same-product at main · laewonJeong/algorithmPractice