[Leetcode]1512. Number of Good Pairs

1. problem : 

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

 

2. solution 1 : 

public class Solution {
    public int numIdenticalPairs(int[] nums) {
        int ans = 0;
        int[] cnt = new int[101];
        for (int num : nums) {
            ans += cnt[num]++;
        }
        return ans;
    }
}

이 문제의 solution은 leetcode의 다른 사람이 작성한 solution이다. 이 solution은 매우 특이하다. 그 이유는 cnt라는 101개의 원소가 들어갈 수 있는 배열을 만든다. 처음에는 이게 뭐지?라고 생각하고 코드를 해석하기 시작했다. 5분 정도 이해가 되지 않았다. for 문을 잘 보면, ans += cnt [num]++ 이 구문이 있는데, cnt [num]++는 후위증감 연산자다. 즉 ans에 cnt [num]을 더한 후, cnt [num] 값을 하나 증가시킨다. 

0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0

0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0

 

자 101개의 원소가 들어갈 수 있는 배열을 여기에 표현하기는 힘들다. (참고로, 101개는 문제 제한조건에서 nums의 길이는 100개이기 때문이다.) 

이제 해석해 보자 nums = [1,2,3,1,1,3]이라고 가정하자. 그러면 첫 번째, a = 1일 것이다. 이제 ans += cnt [1]++ 의 결괏값은 ans = 0 , cnt [1]는 1이 될 것이다. 

 

0	1	2	3	4	5	6	7
0	1	1	0	0	0	0	0

 

그럼 이제 이렇게 값이 바뀔 것이다. 여기서 다음 a = 2가 된다. 이 과정의 결괏값은 ans = 0 , cnt [2] =1이 된다. 

 

0	1	2	3	4	5	6	7
0	1	1	1	0	0	0	0

 

다음으로 , a = 3이 된다. 이때 결괏값은 ans = 0 , cnt [3] = 1이 된다. 

 

0	1	2	3	4	5	6	7
0	2	1	1	0	0	0	0

 

다음으로, a = 1이 된다. 이때 결괏값은 ans = 1 , cnt [1] = 2이 된다. 즉, cnt에 1이 하나 더 들어갈 것을 예상하고, cnt에 1을 증가하기 전에 ans에 1을 증가시킨다. 쉽게 설명해 보면, cnt [1]을 봤더니 , 이미 1이 있네? 그럼 내가 들어가면 나랑 값도 같고, index i < j 조건도 만족하니, 너랑 나랑은 짝이 될 수 있겠네? 그러면 1쌍을 ans에 추가하자! 이렇게 해석된다. 

 

0	1	2	3	4	5	6	7
0	3	1	1	0	0	0	0

 

다음으로, a = 1이다. 이때 결괏값은 ans = 3, cnt [1] = 3이 된다. 쉽게 설명해 보면, 1이 cnt [1]에 들어가려고 봤더니, 이미 2가 있네? index 조건도 만족하고, 값도 같으니, 너네 2명 나랑 각각 pair로 볼 수 있겠네! 그럼 2개 추가하고 와! 이렇게 해석된다. 

 

0	1	2	3	4	5	6	7
0	3	1	2	0	0	0	0

 

다음으로, a = 3이다.  이때 결괏값은 ans = 4, cnt [3] = 2가 된다. 쉽게 설명해 보면, 3이 cnt [3]에 들어가려 했더니, 어? 1개가 있네? 그럼 너랑 나랑은 짝이 될 수 있겠다. 어서 ans에 1을 더하고 오렴! 그다음에 내가 들어갈게!! 이렇게 해석할 수 있다. 

마지막으로 , ans를 return 하면 good pair를 모두 구할 수 있게 된다. 

 

3. solution 2 : 

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

 사실, 이 코드는 내가 짠 코드다. 시간복잡도는 O(n^2)이다. 위의 solution1은 O(n)이다. 

그래서, 이 코드는 그냥 참고용으로만 적어봤다. 

설명을 조금 해보자면, 중첩 loop를 통해 각각의 값을 비교해 조건에 만족하면 count값에 1을 더하는 간단한 코드다.