1512-kir3i.md

1512. Number of Good Pairs

Solution

• 시간복잡도: O(N)

• 알고리즘

  구현, 수학

• 풀이설명

  1. 같은 nums 값을 가진 집합의 크기를 구한다. 이를 리스트 cnts에 저장한다.
  2. cnts의 각 요소를 순회하며 값이 2 이상이면 $_nC_2$만큼의 경우의 수가 추가된다. 따라서 cnts를 순회하며 값이 2 이상인 경우에만 ans에 $_nC_2$를 더한다.

• 소스코드

class Solution:
    def numIdenticalPairs(self, nums):
        cnts = [0] * 101
        for x in nums:
            cnts[x] += 1

        ans = 0
        for cnt in cnts:
            if cnt > 1:
                ans += self.nC2(cnt)
        return ans

    def nC2(self, n):
        return n*(n-1)//2