[LeetCode] 1512. Number of Good Pairs

https://leetcode.com/problems/number-of-good-pairs/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 배열 / 구현

문제 난이도 : Easy

 

문제

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

 

정수 배열 nums가 주어집니다.

좋은 페어를 구하시오.

좋은 페어(i, j)란 값이 같고 j가 i 뒤에 있는 경우를 말합니다.

 

풀이

조합을 이용한 풀이 - 각 숫자별로 개수를 구해놔서, 각 숫자들을 n이라고 했을 때, nC2(조합)을 구한다.

 

누적하는 방식 - 각 숫자가 등장할 때마다 기존에 등장한 숫자들과의 쌍을 만들 수 있으므로, 새로 발견된 숫자가 등장한 경우에는 기존의 숫자들과의 조합을 누적하면 된다. 새로운 숫자가 나타날 때마다 이미 나온 숫자들과의 조합을 더하여 좋은 쌍의 수를 누적하는 방식.

(n번째로 숫자를 찾으면, N-1개를 누적시킴.)

 

코드

C++

조합을 이용한 코드

class Solution {
public:
    int nCr(int n, int r) {
        int result = 1;
        for (int i = 1; i <= r; ++i)
        {
            result *= n - i + 1;
            result /= i;
        }
        return result;
    }
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> um;
        set<int> s;

        int pairs = 0;

        for(const auto& num : nums) {
            um[num]++;
            s.insert(num);
        }

        for(const auto& num : s) {
            if(um[num] >= 2) {
                pairs += nCr(um[num], 2);
            }
        }

        return pairs;
    }
};

누적하는 코드

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> um;
        int pairs = 0;

        for(const auto& num : nums) {
            pairs += um[num];
            um[num]++;
        }

        return pairs;
    }
};