1512. Number of Good Pairs 파이썬 defualtdict 이용해서 해시로 풀기

 

Number of Good Pairs - LeetCode

 

 

<처음 풀이>

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] == nums[j] and i<j:
                    count+=1

        return count

문제에 적힌대로 풀면 통과는 되지만 시간복잡도가 O(n^2)인 말 그대로 복잡한 풀이..

 

 

<배운 풀이>

from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:        
        count_dict = defaultdict(int)
        count = 0
        for num in nums:
            count += count_dict[num]
            count_dict[num] += 1
        return count

 

해시맵(딕셔너리)를 사용해서 각 숫자가 누적 몇 번 출현했는지를 저장한다.

시간복잡도를 O(n)으로 줄일 수 있다.

 

 

1. count_dict = 각 숫자의 출현 횟수를 저장하는 딕셔너리 설정, 처음에는 모두 0으로 int초깃값을 준다.

2. count는 좋은 쌍의 개수를 저장하는 변수이다.

 

3. 배열 nums를 순회하면서 count_dict[num] 값을 count에 더한다. 현재 숫자가 지금까지 몇 번 출현했는지에 따라 좋은 쌍의 개수를 증가시키는 것.

4. 그 후에 count_dict[num] 값을 1 증가시킨다.

 

5. 모든 숫자를 순회한 후, count를 반환한다.