1512. Number of Good Pairs

문제

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

풀이

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int answer = 0;

        for(int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        for(int value : map.values()) {
            if(value >=  2) {
                answer += function(value);
            }
        }

        return answer;


    }

    private int function(int n) {
        if(n == 2) return 1;
        return function(n - 1) + n - 1;
    }
}

• 재귀를 이용한 풀이
  

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int answer = 0;

        for(int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        for(int value : map.values()) {
            if(value >=  2) {
                answer += (value * (value - 1))/2;
            }
        }

        return answer;
    }
}

• nCr = (n * (n-1)) / r