K-diff Pairs in an Array

K-diff Pairs in an Array

Explore - LeetCode

- 문제 내용 : 숫자의 배열과 목표로 하는 Target Value를 주었을 때, 숫자의 배열에서 선택한 2개의 값의 차로 Target Value를 만드는 방법의 수를 나타내시오. 

 

- 접근 방법

• 모든 경우의 수
• Sorting
• Target 값 Tracking 

모든 경우의 수는 N^2로 for를 2번 돌면 되기 때문에 달리 언급 하지 않겠다.

Sorting 처리의 경우 다음과 같은 전제 사항을 갖고 접근이 가능하다.

가장 낮은 값에서 Target값에 도달 가능한 경우만 값을 찾는다.

예를 들자면 다음과 같은 

nums = [3,1,4,1,5], k = 2

문제가 주어진다면, 찾고자 하는 값은 

[1,-1,2,-1,3]

이 되게 된다. 이를 Sorting해서 처리 하게 되면 다음과 같다.

[1,1,3,4,5] => 찾고자 하는 값 [-1,-1,1,2,3]

1과 3을 찾을 수 있음으로 정답은 2가 된다.

1번 Sorting 처리를 함으로 시간 복잡도는 O(NlogN) 이다.

var findPairs = function(nums, k) {
    nums = nums.sort((a,b)=>a-b);
    let map = new Map();
    let set = new Set();

    for(let i = 0; i < nums.length; i++){
        let remainder = nums[i] - k;
        if(map.has(remainder)){
            set.add(JSON.stringify([remainder, nums[i]]));
        }
        map.set(nums[i],true);
    }

    return set.size;
};

그런데 만약 하단이 아니라 상단을 찾는 경우는 어떻게 될까?

nums = [3,1,4,1,5], k = 2

에서 찾고자 하는 값은

[5,3,6,3,7] 이 될 것이고 [5,3,6,3,7]

5하나와 3하나를 찾을 수 있기 때문에 정답 2가 가능하다.

그런데 이경우는 Target이 0인경우 답을 찾기 어렵다.

nums = [3,1,4,1,5], k = 0

찾고자 하는 값은 [3,1,4,1,5] 이 된다.

1이 2번 나온 경우만 0이 가능하다. 2개를 선택하기 때문에 k가 0일경우는 무조건 자신과 같은 값이 2개 이상이어야 한다.

이것을 정리하자면

• k값이 0 이상이고, 선택된 값 + k값 = 목표값 : 이 존재 한다면 count + 1
• k값이 0이고, 자신과 같은 값이 2회 이상 나온다면 count + 1

코드로는 아래와 같이 나타낼 수 있다.

var findPairs = function(nums, k) {
    let map = new Map();

    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], ~~map.get(nums[i]) + 1);
    }

    let result = 0;
    for (let [key, value] of map.entries()) {
        if (k == 0 && 1 < value) {
            result ++;
        }

        if (0 < k && map.has(key + k)) {
            result ++;
        }
    }
    
    return result;
};

마지막으로 하단과 상단을 같이 찾는 다면 어떻게 될까?

주어진 값

nums = [3,1,4,1,5], k = 2

에서 찾고자 하는 하단은

[1,-1,2,-1,3]

이고, 찾고자 하는 상단은

[3,1,4,1,5]

이다.

상기 2가지 경우의 

다음과 같은 Pair로 표현이 가능하다.

• case 1) 하단 1일때 상단 3
• case 2) 하단 3일때 상단 5
• case 3) 그리고 상단 3일때 하단 1

여기서 case1과 3은 동일 결과 값임으로 이를 처리해 줘야 한다.

이를 해결하는 방법은 상단에서 하단으로 Pair를 찾은 경우는 상단만 처리 하는 것이다.

반대로 하단 값만 Pair로 처리 해도 결과는 같게 된다.

상단만 Pair 처리 하게 되면 [3,5] 가 답이 되고

하단만 Pair 처리 하게 되면 [1,3]이 답이 된다.

var findPairs = function(nums, k) {
    let set = new Set();
    let result = new Set();

    for(let i = 0; i < nums.length; i++){

        if(set.has(nums[i] + k)){
            result.add(nums[i]+k);
        }

        if(set.has(nums[i] - k)){
            result.add(nums[i]);
        }

        set.add(nums[i]);
    }

    return result.size;
};

코드는 상기와 같고 O(N)으로 가장빠른 속도를 갖는다.