99클럽 코테 스터디 17일차 1512. Number of Good Pairs

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

 

좋은 쌍의 수 (Number of Good Pairs)

문제 설명:

주어진 정수 배열 nums에서, (i, j)의 쌍이 다음 조건을 만족할 때 "좋은 쌍"이라고 부릅니다:

• 0 <= i < j < nums.length
• nums[i] == nums[j]

좋은 쌍의 총 개수를 반환하세요.

제약 사항:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

 

풀이

 

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        # 숫자의 빈도를 저장할 딕셔너리
        frequency = defaultdict(int)
        
        # 배열을 순회하며 빈도 계산
        for num in nums:
            frequency[num] += 1
        
        # 좋은 쌍의 수를 계산
        good_pairs = 0
        for count in frequency.values():
            if count > 1:
                good_pairs += count * (count - 1) // 2
        
        return good_pairs

 

 

알아야하는 수학 지식

중복되는 쌍의 개수가 c(count)개라면, 이중 두 개를 선택할 수 있는 경우의 수는 c(c-1) / 2 이다.

이는 중고등학교 때 배운 조합의 개념이 들어간다.

 

c개 중 2개를 선택하는 경의 수 이므로 C(c,2) 이다.

 

C(n,2)는 다음과 같은 계산이 가능하다.