[Leetcode / Python] 2364. Count Number of Bad Pairs

난이도 : medium

 

리스트 nums에서 (j > i) num[j] -num[i] != j - i인 쌍을 찾는 문제

 

리스트 nums에서 2개의 요소로 이루어진 total 수에서 num[j] -num[i] = j - i 인 쌍을 빼면 될 것.

num[j] - j = num[i] - i = a라고 해석할 수 있는데,

이 a값으로만 이루어진 요소가 몇 개인지 count 후 count * (count -1 ) / 2를 취한 값을 sum하면 풀린다.

from collections import Counter
class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)
        total = n * (n - 1)// 2
        count = Counter([nums[i] - i for i in range(n)])
        return total - sum([(val - 1) * val // 2 for key, val in count.items() if val > 1])

1. total = n * (n - 1) // 2
2. nums[i] - i를 Counter 취함
3. count 딕셔너리에서 val값이 1 초과인 값으로 이루어진 요소의 갯수를 일일히 sum한 후, total에서 빼줌

Runtime : 55ms (96.98%)

Memory : 39.30MB (8.95%)