Daily Leetcoding Challenge 1512. Number of Good Pairs

바쁜 일정으로 포스팅을 못하고 있었는데 추석 연휴까지 겹치면서 오랜만에 쓰게 됐다. 매일 한 문제씩만이라도 풀려고 하는데 꾸준히 하기가 참 어렵다. 

LeetCode - The World's Leading Online Programming Learning Platform

직관

주어진 배열에서 Good pair 정의에 맞는 숫자 쌍의 개수를 찾는 문제다.

인덱스가 i < j 인 순서 쌍 (i, j)는 nums[i] == nums[j] 일 때 Good Pair이다.

pair를 찾는 직관적인 방법은 이중 반복문을 돌려서 찾는 방법이 있고, 해시맵을 사용해서 값을 저장한다면 속도를 개선할 수 있을 것 같다.

배열을 순회하면서 출현하는 숫자의 횟수를 countMap에 저장해보자. j번째 인덱스의 숫자 nums[j]가 이전에 count 값만큼 출현했다면, j로 만들 수 있는 순서 쌍이 count 값만큼 존재한다는 뜻이다.

접근법

1. ans=0, Map<Integer, Integer> 인 countMap을 초기화한다.

2. 배열 nums의 j번째 숫자 nums[j]에 대해서

  2-1. countMap에서 nums[j]의 출현 횟수를 가져오고, 없으면 0으로 count를 초기화한다.

  2-2. ans에 count를 더한다.

  2-3. countMap에 nums[j]의 출현 횟수를 count+1로 업데이트한다.

3. ans를 반환한다.

복잡도

첫번째 솔루션의 시간 복잡도는 O(n^2), 공간 복잡도는 O(1)이고 두 번째 솔루션의 시간 복잡도는 O(n), 공간 복잡도는 O(n)이다.

코드

86.48%

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int len = nums.length;
        int ans = 0;
        for(int i=0; i<len-1; i++) {
            for(int j=i+1; j<len; j++) {
                if (nums[i] == nums[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

100%

    public int numIdenticalPairs(int[] nums) {
        int ans = 0;
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int j=0; j<nums.length; j++) {
            int count = countMap.getOrDefault(nums[j], 0);
            ans += count;
            countMap.put(nums[j], count+1);
        }
        return ans;
    }