Hackerrank - pairs

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

Pairs | HackerRank

function pairs(k,arr){
    arr.sort((a,b)=>a-b);
    let start = 0;
    let end = 0;
    let cnt = 0;
    while(end<arr.length){
        let cal  =arr[end]-arr[start];
        if(cal<k){
            end++;
        }
        if(cal>k){
            start++;
        }
        if(cal==k){
            end++;
            cnt++;
        }
    }
    return cnt;
}

 투포인터를 사용해 풀 수 있는 문제였다.

 

1. 배열을 정렬

2. 만약 차이가 K보다 크면  start를, 작으면 end를, 같으면 end와 cnt값을 올려준다.

3. end가 끝에 도달할때까지 반복

 

로 당연히 풀었는데

function pairs(k, arr) {
  const points = new Set(arr);
  let pairs = 0;
  for (let i = 0; i < arr.length; i++) {
    if (points.has(arr[i] - k)) {
      pairs++;
    }
  }
  return pairs;
}

console.log(pairs(2, [1, 5, 3, 4, 2]));

배울 점이 있는 코드가 가져왔다.

 

여기서는 Set와 has를 통해서 풀었다.

 

new Set으로 변환하는 것은 O(n)이고,

 

Set.has는 O(1)을 보장하지는 않지만,

While O(1) complexity isn't guaranteed, the specification requires the method to run in sublinear time. And Set.has(), generally, will perform better than Array.indexOf().

O(n)보다는 적게 걸린다.

 

중복 제거할떄나 has 등으로 검색할 일이 있으면 Set을 사용해보자