[코테 꿀팁] 배열의 원소 찾기에서 시간 초과가 나온다면? Set.has() 생각하기

백준의 10815번 문제를 푸는 과정에서 메모리가 너무 많이 사용되어 이상함을 느껴 다른 풀이를 참고하는 과정에서 Set.has()를 활용하는 방법을 알게 되었고 기록합니다.

 

Set.has() 함수의 역할

집합(Set) 내부에 해당하는 값이 있다면 true, 없다면 false를 반환하는 함수입니다. 마치 Array.includes()와 같은 역할을 합니다.

 

하지만 둘의 방식에는 차이가 있습니다.

 

차이점

includes()의 경우 배열 요소를 돌며 탐색하고 결과를 반환합니다. 따라서 시간 복잡도가 O(n)이 나옵니다.

하지만 has()의 경우 집합은 해쉬 기반 구조를 가지고 있기 때문에 시간 복잡도가 O(1)로 상대적으로 훨씬 빠른 속도를 낼 수 있습니다.

 

주의 사항

하지만 집합의 경우 중복 값을 허용하지 않고, 순서를 보장하지 않습니다. 그렇기 때문에 상황을 고려하여 잘 사용해야 합니다.

 

결론

중복되는 값이 없고, 순서가 상관이 없는 경우인데 데이터의 크기가 커진다? 그럴 때 사용하는 것을 고려해 봅시다.

 

JS에는 여러 도움이 되는 함수가 많으니 공부하며 기억해 보도록 합시다.

MDN-Set