[HackerRank] Pairs

def pairs(k, arr):
    # Write your code here
    # length = len(arr)
    count = 0
    
    new_set = set(arr)
    
    for ele in arr:
        target_one = ele+k
        target_two = ele-k
        
        if target_one in new_set:
            count += 1
        if target_two in new_set:
            count += 1
            
        new_set.remove(ele)
    
    # for i in range(length):
    #     for j in range(i+1,length):
    #         if abs(arr[i]-arr[j]) == k:
    #              count += 1
    return count

이번 문제는 주어진 배열(arr)과 타겟 값(k)가 주어졌을 때, 두 수의 차가 k인 쌍의 개수를 구하는 문제이다.

 

입력 값의 제한 사항에 2 <= n <10^5 일 때부터 눈치는 채고 있었지만, 2중 반복문을 사용하여 완전 탐색(Brute-force) 방식으로 풀이하게 되면 시간초과가 발생한다.

 

따라서 배열의 값들이 고유한 값이기 때문에 집합 자료형(new_set)으로 변환시켜준 후, '배열 값 +- k' 값이 new_set 안에 존재하는지 여부를 체크하고 존재한다면 카운팅(count + 1)을 시켜주면 된다.(집합 자료형의 in 연산자는 평균적으로 O(1)의 시간복잡도를 가진다.)

 

그리고 마지막으로 i 번째 값으로 카운팅을 한 후에 해당 값을 집합에서 제거해주지 않으면 다음 값들이 카운팅할 때 중복될 수 있다.

 

집합 자료형을 사용해서 시간초과를 해결할 수 있었던 좋은 문제였다 :)