K-diff Pairs in an Array [leetcode]

문제 풀이

리스트 안 숫자들 중 차이의 절대값이 k를 만족하는 숫자 쌍 의 개수를 찾는 문제다.

한국말로 한문장 정리하니 “의” 로 연결된게 많아 국어지문 푸는것 같다.

 

다시 정리하자.

• 리스트 안 숫자들 중 ⇒ ex. [3,1,4,1,5]
• 차이의 절대 값 ⇒ ex. |3 - 1| = 2
• k를 만족하는 숫자 쌍 count! ⇒ ex. |3-1| == 2 ? (count +1) : nothing!

문제를 보면 리스트의 중복된 숫자가 있어도 1개로 친다고 한다. 그럼 로직상 중복체크도 필요하다는 얘기다.

 

나는 이렇게 풀었다.

현재 비교할 숫자 = nums[i]

비교 당해야 할 숫자들 = nums[i+1:] (중복을 피하기 위해 i 번째 이후 숫자들만 사용)

• 중복을 피하기 위해 num_set 생성 ⇒ num_set = set(nums[i+1:])
• nums를 순회하기 때문에 이전에 비교를 진행한 숫자를 제외하기 위해 alreay_use_num set 지정
• num_set에 이전에 비교한 숫자가 있을경우, 중복 발생하므로 차집합 연산 진행 (num_set - already_use_set )

k = 0 일경우, 절대값 연산시 자기 자신이므로 num_set에 존재 유무 판단

num - k ⇒ ex. num=3, k=2 일경우, 3-2 = 1 이 num_set에 존재하는지 판단

num + k ⇒ex. num=3, k=2 일경우, 3+2 = 5 가 num_set에 존재하는지 판단

존재하면 count += 1 !

 

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        
        count = 0
        already_use_num = set()
        for i in range(len(nums)):
            num = nums[i]
            if num in already_use_num:
                continue
                
            nums_set = set(nums[i+1:]) - already_use_num
            if k == 0:
                if num in nums_set:
                    count+=1
            else:
                if num-k in nums_set:
                    count+=1
                if num+k in nums_set:
                    count+=1
            already_use_num.add(num)
        return count