[LeetCode] 1726. Tuple with Same Product

https://leetcode.com/problems/tuple-with-same-product/description/

leetcode - Tuple with Same Product

문제 유형: 수학, 해시

문제 난이도: 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.

 

독립적인 정수 배열 nums가 주어집니다.

a*b = c*d인 (a, b, c, d)튜플조합의 개수를 모두 구하시오.

 

풀이

하나의 조합을 구하면, 8개의 튜플을 만들 수 있다.

해시맵[곱] = (만들수 있는 쌍의 수)의 꼴로 저장한다.

2D로 배열을 순회하면서 곱 값의 만들 수 있는 쌍의 수를 누적하면서 저장해준다.

 

이제, 해시맵의 모든 요소들을 확인하면서 count가 2 이상이면, 페어들의 실제 수인 count*(count-1)/2 * 8을 구해서 정답에 누적한다.

 

코드

C++

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> productCount;
        int ans = 0;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int product = nums[i] * nums[j];
                productCount[product]++;
            }
        }

        for (auto& [product, count] : productCount) {
            if (count > 1) {
                ans += (count * (count - 1) / 2) * 8;
            }
        }

        return ans;
    }
};

 

Go

func tupleSameProduct(nums []int) int {
    productCount := make(map[int]int)

    for i, a := range nums {
        for _, b := range nums[i+1:] {
            productCount[a*b]++
        }
    }

    ans := 0
    for _, c := range productCount {
        if c > 1 {
            ans += c*(c-1)*4
        }
    }

    return ans
}