[코테] 해시 문제 유형 정리

이번 주에는 프로그래머스에서 Lv2, JavaScript, '해시' 유형 필터링 걸어서 나온 문제 3개를 모두 풀었다.
공통 유형의 문제들을 풀어보면 그 개념이 감이 올 것으로 예상했는데 그렇지 않아서 따로 정리해보려 한다.

해시 유형의 공통점

이 값이 존재하는가/몇 개인가 를 빠르게 찾아야 할 때, '배열'보다 '해시'를 쓰는 것이 효율적이다!

왜 Map/Hash를 쓰는가

• 배열로도 '이 값이 존재하는가', '몇 개인가'를 찾을 수 있다.

• 최악의 경우 배열의 모든 요소를 순회해야만 답을 구할 수 있다는 약점이 있을 뿐..

• 이것을 시간복잡도로 표현하면, O(n)

• 반면 Map을 사용하면, 키로 바로 접근하므로, O(1)의 시간복잡도를 갖는다.

// 배열
arr.includes("target"); // 최악의 경우 전체 순회

// Map
map.has("target"); // 내부 해시값을 이용해 바로 접근

• 단, 해시 충돌(다른 키가 같은 저장 위치로 계산되는 경우)이 발생하면 최악의 경우 O(n)이 될 수 있음. 코딩테스트 레벨에서는 그런 상황은 없다는 가정 하에 해시 자료구조가 O(1)이라고 전제하는 것임.

해시가 O(1)인 이유

• 해시 자료 구조에서는 키를 넣었을 때 해시 함수가 저장 위치(인덱스)를 계산해줌
• 데이터 인풋할 때도, 데이터를 찾을 때도 해시 함수가 그 저장 위치를 이용하므로 데이터를 순회할 필요가 없는 구조
• JavaScript에서는 Map, Object({})가 내부적으로 해시 구조를 사용함.
  • 다만 코테에서는 순서 보장, 순회 편의성 등을 고려해 Object보단 Map 사용이 편리함
  • Map의 get, set 메서드에서 내부적으로 해시 함수를 사용

해시 유형인지 감 잡기

아래와 같은 요구사항을 마주하면 Map을 우선 떠올려보자.

• "중복을 체크해야 함"
• "그룹별로 개수를 세야 함"
• "어떤 값이 존재하는지 (빠르게 - 당연) 확인해야 함"

=> key로 value를 빠르게 찾는 구조를 만들어야 하는가? 를 생각해보면 됨

다만 전화번호 문제처럼 정렬로 더 깔끔하게 풀리는 경우도 있긴 함에 유의