[LeetCode] 2176. Count Equal and Divisible Pairs in an Array

- Problem

2176. Count Equal and Divisible Pairs in an Array

배열 nums가 주어지고, 임의의 조건을 만족하는 pair의 총합을 구하는 문제다.
조건은 다음과 같다.

• nums[i]==nums[j]를 만족하고, 0 <= i < j < n를 만족하는 pair [i, j]

---

- 내 풀이 1 (brute-force)

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        N = len(nums)
        answer = 0

        for i in range(N-1):
            for j in range(i+1, N):
                if nums[i] == nums[j] and (i*j) % k == 0:
                    answer += 1
        
        return answer

- 결과

• 시간 복잡도: O(N^2)
• 공간 복잡도: O(1)

input으로 주어지는 nums의 길이가 최대 100이기에, 시간 복잡도 O(N^2)인 풀이임에도 해결할 수 있는 문제다.

하지만, input으로 주어지는 nums의 크기가 훨씬 더 큰 값이라면...?
더욱 최적화된 로직을 고민해봐야 한다.

---

- 내 풀이 2 (hash table)

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        seen = dict()
        N = len(nums)
        answer = 0

        for i in range(N):
            if nums[i] not in seen:
                seen[nums[i]] = [i]
            
            else:
                for j in seen[nums[i]]:
                    if (i*j) % k == 0:
                        answer += 1
                        
                seen[nums[i]].append(i)
        
        return answer

- 결과

2번 풀이의 시간 복잡도는 어떻게 될까?
두 개의 간단한 샘플을 살펴보자.

1. nums = [1,2,3,4,5,...,10000]
2. nums = [1,1,1,1,1...,1,1,1]

1번 nums가 인자로 주어진다면 해당 코드의 시간 복잡도는 O(N)이 된다.
2번 nums가 인자로 주어진다면 해당 코드의 시간 복잡도는 O(N^2)이 된다.

1번 풀이는 best, worst case를 막론하고 항상 O(N^2)이 된다.
2번 풀이는 주어진 인자에 따라 시간 복잡도가 O(N)~O(N^2)이 된다. 하지만 메모리 공간을 좀 더 쓰게 된다.

...

그래서 더 최적의 풀이 방법은 없나요?