'2025/05/04'에 해당되는 글 1건

Leetcode Problem:

• Number of Equivalent Domino Pairs

Summary

• Given a list of dominoes, find the number of pairs where one domino can be rotated to be equal to another domino.

Approach

• The approach used is to first count the occurrences of each domino, then calculate the number of pairs by summing up the combinations of each domino, considering that each pair can be represented by two dominoes.

Complexity

• O(n log n) due to sorting, where n is the number of dominoes, and O(1) for the space complexity where n is the maximum possible value of a domino.

Explanation

• The solution works by first creating a hashmap to store the occurrences of each domino
• Then it iterates over the hashmap and calculates the number of pairs for each domino by summing up the combinations of each domino, considering that each pair can be represented by two dominoes
• The time complexity is O(n log n) due to sorting, and the space complexity is O(1) for the hashmap.

Solution Code:

class Solution {
public:
    unordered_map cnt;
    int numEquivDominoPairs(vector>& dominoes) {
        for(int i = 0 ; i < dominoes.size() ; i++){
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            if(a > b){
                int t = a;
                a = b;
                b = t;
            }
            cnt[a*10 + b]++;
        }
        int ans = 0;
        for(auto iter = cnt.begin(); iter != cnt.end(); iter++){
            ans += (iter->second * (iter->second-1)) / 2;
        }
        return ans;
    }
};