Set.has( ) VS Array.includes( )

서론

알고리즘 문제를 풀다가 배열의 요소들을 순회하며 특정 요소를 포함하고 있는지 확인해야 하는 상황이 생겼다.

여기서 가장 먼저 떠오른 것은 Array의 includes( ) 메서드였다.

Array.prototype.includes()

Array 인스턴스의 includes() 메서드는 배열의 항목에 특정 값이 포함되어 있는지를 판단하여 적절히 true 또는 false를 반환합니다.

출처 : MDN 링크

하지만 위의 메서드를 사용하였더니 시간초과가 발생하였다.

왜 그런지 여러가지 글들을 찾아보다가 데이터 타입 중 하나인 Set을 사용하면 데이터 구조를 개선할 수 있다고 한다.

Set

• 데이터 타입 중 하나로 중복되는 값을 가지지 않는 값들의 리스트이다.
• 요소의 순서에 의미가 없으며, 인덱스를 이용하여 요소에 접근할 수 없다.

본론

Array.includes() VS Set.has()

먼저 위의 메서드들의 시간복잡도를 보면 O(n) VS O(1)으로 Set을 사용하는 것이 더 빠르다.

왜 그런가를 알아보자면 Set은 해시테이블(Hash Table) 자료구조를 가지고있어서 그렇다.

Hash Table

• 해시함수를 사용하여 변환한 값을 색인(index)으로 하여 키(key)와 데이터(value)를 저장하는 자료구조를 말한다.

• 검색, 삽입, 삭제에서 평균적으로 O(1)의 시간복잡도를 갖는다.

그러면 무조건 Set을 사용하는 것이 탐색에 있어서 빠를까?

항상 빠르진 않을것이며, 사용하는 상황 / 데이터의 크기에 따라 성능 차이가 나타날 수 있다.

has( ) 보다 includes( )를 사용할만한 상황으로는 아래와 같다.

• 데이터 크기가 작고 무겁게 최적화할 필요가 없는 경우.
• 이미 배열 형태로 데이터가 제공되는 경우.