99클럽(2기) - 코테스터디 18일차 TIL # Array

LeetCode - 1512. Number of Good Pairs

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.

 

---

 

1. 나의 풀이

 nums에 대한 인덱스 i, j를 구하기 위해 이중반복문을 사용했다. 시간복잡도 O(n^2)이다. 

 

1) good_pairs_list 초기화

 'nums[i] == nums[j] and i < j'를 만족하는 (i, j) 쌍들을 저장할 'good_pairs_list'를 초기화한다. 

 

2) nums를 순회해서 good_pairs_list 갱신

 nums의 i번째 인덱스는 0에서 len(nums) - 1까지 순방향으로 진행하고 j번째 인덱스는 모든 i번째 인덱스에 대해 len(nums) - 1에서 i + 1 번째까지 역방향으로 진행하면서 'nums[i] == nums[j] and i < j' 조건을 만족하면 (i, j) 쌍을 good_pairs_list에 추가해준다. nums 순회가 끝나면 good_pairs_list의 요소의 개수를 반환한다.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        good_pairs_list = []
        for i in range(len(nums)):
            for j in range(len(nums) - 1, i, -1):
                if nums[i] == nums[j]:
                    good_pairs_list.append((i, j))
        return len(good_pairs_list)

 

 

2. 챗 지피티의 풀이

이런 방법도 있군! 챗지피티는 defaultdict를 사용해서 시간복잡도 O(n)으로 풀었다.

 

1) good_pairs와 count 초기화

 정답으로 반환할 'nums[i] == nums[j] and i < j'를 만족하는 (i, j) 쌍 개수 'good_pairs'와 파이썬 내장 모듈 defaultdict을 사용해 int를 기본값으로 가지는 딕셔너리 'count'를 초기화한다. count에는 nums의 요소 num이 키로, 해당 num이 중복되는 횟수가 값으로 들어갈 것이다. 

 

2) nums를 순회하면서 good_pairs와 count 갱신

 nums의 요소들을 순회하면서 good_pairs에 num이 중복되는 횟수를 더해준다. defaultdict 파라미터로 int를 전달했기 때문에 최초 키에 대한 값은 숫자 0이다. 즉, nums의 첫번째 요소 num에 대해서 count[num] = 0이다. good_pairs를 갱신해줬으면 count[num]에도 1을 더해준다. nums의 모든 요소에 대해서 반복이 끝나고 최종적으로 갱신된 good_pairs를 반환한다.

from typing import List
from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        good_pairs = 0 # 'nums[i] == nums[j] and i < j'를 만족하는 (i, j) 쌍 개수
        count = defaultdict(int) # num을 키로, num이 반복되는 횟수를 값으로 가지는 딕셔너리
        
        for num in nums:
            good_pairs += count[num]
            count[num] += 1
        
        return good_pairs

 

 

3. 느낀점

 defaultdict의 존재는 알았지만 defaultdict의 사용법을 떠올리지 못 했다. defaultdict의 파라미터로 int를 전달하면 첫 번째 키에 대해서 숫자 0을, list를 전달하면 빈 리스트 []를, str을 전달하면 빈 문자열 ""를 기본값으로 갖는 딕셔너리가 생성된다. 다음에 defaultdict를 사용할 수 있는 문제가 나오면 꼭 써봐야겠다.