Array vs HashTable

25.03.13

프로그래머스에서 '배열의 원소 삭제하기' 를 하다가 의문점이 들었다.

Q)
let arr = [293, 1000, 395, 678, 94]
let delete_list = [94,777,104,1000,1,12]
// arr 에 있는 것 중 delete_list의 원소를 모두 삭제하고 arr의 순서를 유지

A)
return arr.filter(x=>{
    return delete_list.indexOf(x) < 0
})

나는 이런 식으로 indexOf 를 사용했는데, 이러면 배열 전체를 탐색하면서 시간 복잡도가 O(n)이 나오게 된다.
최악의 경우 배열 끝까지 탐색해야하는데, 더 좋은 효율을 가질 수는 없을까 고민해보았다. 이 때 찾은게 HashTable 구조를 활용하는 것이다.

HashTable 이란 Key-value 쌍을 저장하는 자료구조인데, 해시 함수를 사용해서 데이터를 빠르게 가공할 수 있다.
간단하게 말하자면 해시 함수가 Key 를 고유한 숫자(해시 값)으로 변환하는 것이다.
해시값을 이용하기 때문에 빠르게 접근이 가능하다.

데이터를 검색해야하는 문제에서는 키를 해시 함수에 넣어 해시 값(인덱스)를 계산해서 해당 인덱스에 바로 접근하기 때문에 전체를 탐색할 필요가 없어진다.
JS 에서는 Set과 Map 이 해시 테이블을 사용한다.
작은 배열에서는 .includes 를 사용해도 관계없지만 다량의 데이터를 다루는 실무에서는 Set 을 사용하면 중복제거도 함께 가능하니 .has 를 사용해야겠다고 생각했다.

A)
// [...new Set(delete_lsit)] : 중복을 제거한 Set을 만든 후 만들어진 Set 을 배열로 변환
// new Set(delete_list) : 중복을 허용하지 않는 자료형인 Set 을 생성

// .has 를 사용할 수 있는건 자료형인 Set에서 사용이 가능

const deleteSet = new Set(delete_list);
let ans = arr.filter(x=> !deleteSet.has(x))