LeetCode 532 K-diff Pairs in an Array

https://leetcode.com/problems/k-diff-pairs-in-an-array/

K-diff Pairs in an Array - LeetCode

일단은 정렬, 이분탐색을 활용하는 문제이다. 여기에 조금 더 생각을 붙여야 한다. unique한 페어를 리턴해야하기 때문이다.

 

이분탐색을 하고자 한다면, 이분탐색을 행하는 배열 등이 정렬되어 있어야 한다. 그래서 이분탐색과 정렬은 붙어다닐 수 밖에 없다. 두 수의 차가 k가 되려면, k + 작은 수 = 큰 수로 볼 수 있다. 그러면 절대값은 생각하지 않아도 된다. 목표하는 수가 어디에 있는지 찾기 위해 이분탐색을 행하고, 다음의 3가지 조건을 확인한다.

1. 목표값 위치를 나타내는 인덱스가 현재 작은 수의 인덱스와 같진 않은지 (페어이므로 서로 다른 수가 선택되어야 한다.)

2. 방문체크가 안되어있는지 (아래에서 설명하겠다)

3. 이분탐색 결과 인덱스가 가리키는 값이 목표값과 실제로 같은지

 

위의 3가지 조건을 만족할 경우, 유니크 페어를 만들었다고 볼 수 있게 된다.

 

그리고 다음의 실수에 유의하여야 한다.

- 숫자를 순서대로 정렬한 후에, 이분탐색을 행할 때, 자신보다 뒤쪽의 숫자들만을 대상으로 이분탐색을 행하는 것

=> 이는 같은 수가 여러번 나왔을 때, 중복 페어를 만들게 되어 옳지 않다. 그냥 전 범위로 이분탐색을 행해서 항상 같은 수에 떨어지도록 하는게 낫다. 그래서 필자는 방문체크를 도입했다. 중복 페어가 나오게되면 계속 같은 값으로 떨어지기 때문에, 중복을 피할 수 있게 된다.

 

- 이분탐색 결과 인덱스와 작은 수의 인덱스가 서로 같은지 체크하지 않는 것

=> 이것은 k가 0인 경우에 대비한다. k가 0이면 이분탐색 결과 인덱스가 자기 자신으로 나오게 된다. 페어이어야 하므로 당연히 자기 자신과 페어를 이룰 수 없다.

 

 

< 주요 알고리즘 >

정렬, 이분탐색

 

<코드>

자바스크립트

const merge = (a, b) => {
    let i = 0, j = 0, al = a.length, bl = b.length, ret = []
    while (i < al && j < bl) {
        if (a[i] < b[j]) ret.push(a[i++])
        else ret.push(b[j++])
    }
    while (i < al) ret.push(a[i++])
    while (j < bl) ret.push(b[j++])
    return ret
}

const merge_sort = arr => {
    if (arr.length <= 1) return arr
    let mid = parseInt(arr.length / 2)
    return merge(merge_sort(arr.slice(0, mid)), merge_sort(arr.slice(mid, arr.length)))
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function (nums, k) {
    nums = merge_sort(nums)
    let ans = 0
    const vis = new Array(nums.length).fill(false)

    const bs = v => {
        let s = 0, e = nums.length, ret = 0
        while (s < e) {
            const mid = parseInt((s + e) / 2)
            if (nums[mid] <= v) {
                ret = mid
                s = mid + 1
            } else e = mid
        }
        return ret
    }

    for (let i = 0; i < nums.length; ++i) {
        const idx = bs(nums[i] + k)
        if (idx != i && !vis[idx] && nums[idx] === nums[i] + k) {
            vis[idx] = true
            ans++
        }
    }
    return ans
};