해시(Hash)

[lukasjhan]

해시

특징

해시 문제를 볼 때 가장 중요한 것은

• 데이터를 키-값 쌍으로 저장했을 때 이점이 있는지 확인하기
• 빈도수 계산이나 그룹화가 필요한지 확인하기
• O(1) 시간 복잡도로 조회/검색이 필요한지 확인하기

이러한 특징들이 보인다면 해시 자료구조를 활용하는 것을 고려해볼 수 있다.

문제로 부터 유추할 수 있는 키워드

문제에서 해시 유형임을 파악할 수 있는 핵심 키워드와 특징은 다음과 같다.

• 데이터 조회/검색 관련 키워드
  • "특정 원소가 속한 그룹을 찾으시오"
  • "중복된 원소를 제거하시오"
  • "이미 등장한 적이 있는 원소를 찾으시오"
  • "각 원소의 짝을 찾으시오"
• 개수 세기 관련
  • "조건을 만족하는 쌍의 개수를 구하시오"
  • "가장 많이 출현한 K개의 원소를 찾으시오"
  • "배열에서 [조건]을 만족하는 부분 배열의 개수는?"
• 그룹화/집계 관련
  • "각 [조건]별로 합계를 구하시오"
  • "동일한 패턴을 가진 문자열들을 그룹화하시오"
  • "모든 아나그램을 그룹으로 묶으시오"
  • "[조건]이 같은 원소들의 개수를 구하시오"

푸는 방법

1. Map을 사용해야하는지 Set을 사용해야하는지 확인

Map을 사용하는 경우

• 키-값 쌍이 필요할 때
• 등장 횟수를 세야 할 때
• 그룹별 집계가 필요할 때

Set을 사용하는 경우

• 단순 중복 제거가 필요할 때
• 특정 값의 존재 여부만 확인할 때
• 교집합, 합집합 등 집합 연산이 필요할 때

2. 키(Key) 찾기

• 무엇을 기준으로 데이터를 찾을 것인지 결정
• 어떤 값으로 해시 테이블을 만들지 결정

3. 탐색 및 문제 해결

• 만든 해시 자료구조를 활용해 문제 해결