#해시

해시 테이블과 집합으로 문자열·검색 문제를 빠르게 해결하는 방법을 정리한다. 현재 9개의 풀이가 있다.

LeetCode 217 Contains Duplicate에서 이미 확인한 값을 해시 집합에 기록해 중복을 찾는다. 정렬 없이 평균 O(n) 시간, O(n) 공간으로 판정하는 방법을 소개한다.

LeetCode 2013 Detect Squares에서 좌표별 점의 개수를 중첩 해시에 저장한다. 쿼리 점과 대각선을 이루는 후보와 중복 점의 빈도를 이용해 축에 평행한 정사각형 수를 센다.

LeetCode 49 Group Anagrams에서 각 단어의 문자 빈도를 튜플 키로 바꿔 애너그램을 묶는다. 정렬 없이 O(mn) 시간에 그룹을 만드는 방법을 살펴본다.

LeetCode 347 Top K Frequent Elements에서 해시로 빈도를 세고 빈도별 버킷에 값을 모은다. 비교 정렬이나 힙 없이 O(n) 시간에 상위 k개 원소를 찾는다.

LeetCode 242 Valid Anagram에서 한 빈도 배열에 첫 문자열은 더하고 둘째 문자열은 뺀다. 소문자 영어 조건을 이용해 정렬 없이 O(n) 시간, O(1) 공간에 판정한다.

LeetCode 36 Valid Sudoku에서 한 번의 격자 순회로 행·열·3×3 박스별 중복을 검사한다. 박스 인덱스를 계산해 해시 집합으로 숫자 충돌을 판별한다.

프로그래머스 베스트앨범에서 장르별 재생 합계를 구하고, 장르 안의 곡을 재생 수와 고유 번호로 정렬한다. 장르마다 상위 두 곡을 고르는 과정을 설명한다.

프로그래머스 의상에서 종류별 개수를 센 뒤 각 종류의 선택지를 곱하고, 아무것도 고르지 않은 경우를 뺀다. 곱셈 법칙으로 조합 수를 계산한다.

프로그래머스 '중요한 단어를 스포 방지'에서 단어와 스포일러 구간의 겹침을 찾고, 해시 집합으로 일반 영역의 단어와 중복을 처리한다.

해시 테이블 학습 가이드

필요한 주제만 펼쳐서 해시 테이블의 구조와 빠른 조회 패턴을 익힌다.

해시 테이블 기본 개념

해시 테이블은 키를 해시 함수로 변환해 저장 위치를 정하고, 나중에 같은 키로 해당 위치를 빠르게 찾아가는 자료구조다.

Python에서는 `dict`가 키와 값을 저장하고, `set`이 원소의 존재 여부를 빠르게 확인하는 대표적인 해시 기반 자료구조다.

충돌과 키 비교

서로 다른 키가 같은 버킷 인덱스로 변환되는 것을 충돌이라고 한다. 충돌이 발생해도 실제 키를 다시 비교해 원하는 항목을 구분해야 한다.

Python의 `dict`와 `set`은 충돌 처리를 내부에서 담당한다. 문제 풀이에서는 해시 함수 자체를 구현하기보다, 서로 다른 상태가 같은 키가 되지 않도록 키를 설계하는 것이 중요하다.

자주 사용하는 해시 패턴

시간 복잡도와 사용 기준

해시 테이블의 삽입, 조회, 삭제는 평균적으로 `O(1)`이다. 다만 충돌이 과도하거나 해시 키를 만드는 비용이 크면 실제 성능이 달라질 수 있다.

정렬이 필요한 문제나 값의 순서 관계를 계속 비교해야 하는 문제에서는 해시만으로 해결되지 않을 수 있으므로 정렬, 힙, 트리와 비교한다.

자주 하는 실수