[Hackerrank] pairs

https://www.hackerrank.com/challenges/pairs/problem

Pairs | HackerRank

풀이

• Input : 두 개 숫자의 차이 k, 숫자 배열 arr
• arr에 있는 두 개의 숫자의 차이가 k인 모든 경우의 수를 구하는게 문제
• 시간복잡도를 줄이는 문제로, 2중 반복문으로는 통과할 수 없음 -> O(NlogN) 이하 필요
• python인 경우, set자료구조에서 교집합을 구할 때의 시간복잡도는 두 개 리스트 길이의 합.
  • O(len(s) + len(t))
• set의 자료구조를 사용해 전체 item에 k를 더한 집합과 원래의 집합의 교집합을 구해줌으로써 시간복잡도를 줄일 수 있음
• 시간복잡도 : O(3N)
  • set(arr) : O(N) ; N은 arr의 길이
  • set([item + k for item in set(arr)]) : O(N)
  • set(set(arr) & set([arr+k인 리스트]) ) : O(2N)
  • len(arr) : O(1)

def pairs(k, arr):
    return len(set(arr) & set([item + k for item in set(arr)]))