[99클럽] 코테 스터디 26일차 TIL - 배열(1512. Number of Good Pairs)

문제

문제 설명

배열 nums[]가 주어질 때 good pairs의 개수를 반환하라.
good pairs: nums[i] == nums[j] and i < j

예시

• Example 1:
  Input: nums = [1,2,3,1,1,3]
  Output: 4
  Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
• Example 2:
  Input: nums = [1,1,1,1]
  Output: 6
  Explanation: Each pair in the array are good.
• Example 3:
  Input: nums = [1,2,3]
  Output: 0

제약 조건

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

풀이 방법

코드

• 내 풀이 - 시간복잡도 O(n^2)
  • 가장 쉽게 생각할 수 있는 방법이다.
  • 이중 반복문을 이용하여 nums[i]의 값과 nums[j]의 값을 비교하여 같다면 good pairs++
  • return good pairs

// 시간복잡도 : O(n^2)
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    result++;
                }
            }
        }
        return result;
    }
}

• 다른 풀이 - 시간복잡도 O(n)
  • count: good pairs 변수의 개수를 저장
  • freq[] : 각 숫자의 출연 횟수
  • 코드 로직
    • nums[]를 순회하면서 freq[num]의 값을 count에 더한다.
    • freq[num]의 값을 1 증가 시킨다.
    • 결론: good pairs의 총 개수를 count에 저장한 후 count를 반환한다.
  • 예시
    • nums = [1, 2, 3, 1] 이라면
      • count = 0 초기화
      • freq[101] = 0 초기화
      • nums[]를 순회하면서
        • num = 1일 때, freq[1]은 0이므로 count += 0 & freq[1]을 1로 증가
        • num = 2일 때, freq[2]는 0이므로 count += 0 & freq[2]를 1로 증가
        • num = 3일 때, freq[3]은 0이므로 count += 0 & freq[3]을 1로 증가
        • num = 1일 때, freq[1]은 1이므로 count += 1 & freq[1]을 2로 증가
      • return count(1)

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int count = 0;
        int[] freq = new int[101];

        for (int num : nums) {
            count += freq[num];
            freq[num]++;
        }

        return count;
    }
}

오늘 회고

문제 자체는 매우 쉽게 풀었다.
그런데 다른 사람들의 풀이를 보니 시간복잡도가 O(n)인 방법이 있었다.
다른 방법은 생각도 못했는데 ..
앞으론 문제를 풀고 더 효율적인 방법이 있는지 고민해보는 시간도 가져야겠다.
오늘도 고생했다 ~😊