[LeetCode] 2150. Find All Lonely Numbers in the Array - 자바스크립트 0630

https://leetcode.com/problems/find-all-lonely-numbers-in-the-array/

Find All Lonely Numbers in the Array - LeetCode

오늘 비슷한문제의 easy문제를 풀었었는데.. 이 문제에서도 처음 풀이를 할 때 시간초과가 나왔다.. ㅠㅠㅠ 초과가 나온풀이는

var findLonely = function (nums) {
    const unique = distinct(nums)
    return nums.filter((x, index) =>
        !nums.includes(x + 1) && !nums.includes(x - 1) && unique.has(x)
    )
};
function distinct(arr) {
    const distinct = new Set()
    const overlap = new Set()
    arr.map(x => (!distinct.has(x) && !overlap.has(x)) ? distinct.add(x) : (
        distinct.has(x) && !overlap.has(x) ?
            (distinct.delete(x), overlap.add(x)) : null
    ))
    return distinct
}

눈물.. 근데 오늘 이런 문제를 두문제를 풀면서 왜 이런 시간 초과가 나올까? 라고 생각을 하던중 생각이 든것은

Has vs Includes

이 둘의 차이는 object에서 사용한다 has, array에서 사용한다 includes이다. 그렇다면 object와 array의 차이는 무엇일까?

Array.from을 써보면 알 수 있지만, Array는 index를 키로 가지고 있는 Object이다.

즉, includes는 value에 있는 검색을 하기 위해서 (최악의 경우, array가 가지고 있는 length 모두)  value를 검색해야한다.

예시를 들자면 [1,2,3,4,5,6,7].includes(7)과 같은경우 1부터 7까지 7회를 시행해야한다.

Has 같은 경우(map의 get도 같다) key값을 입력하고 없으면 끝!  즉 1과 n과의 차이이다.

앞으로는 순서가 필요가 없다면 Object를 이용해서 풀어야겠다.

 

---

지금부터 풀이를 시작하겠습니다

1. 갯수 체크를 위하여 map을 만들어서 갯수를 저장합니다.

function distinct(arr) {
    const result = new Map()
    arr.map((x) => result.set(x, (result.get(x) || 0) + 1))
    return result
}

2. 위에 구한 맵에서 값이 1이거나, 넣은 숫자보다 -1인 숫자가 없거나, 넣은 숫자보다 +1인 숫자가 없는 경우를 filter하고 리턴한다.

var findLonely = function (nums) {
    const unique = distinct(nums)
    return nums.filter((element) => unique.get(element) === 1 && !unique.get(element - 1) && !unique.get(element + 1))
};
function distinct(arr) {
    const result = new Map()
    arr.map((x) => result.set(x, (result.get(x) || 0) + 1))
    return result
}