해시 테이블은 키를 값에 매핑시킬 수 있는 구조를 가진 자료구조이다.
대부분의 연산의 시간 복잡도는 O(1)를 가진다. 따라서 빠른 성능을 기대할 수 있다.
해시
: 임의 크기 데이터를 고정 크기의 값으로 매핑하는데 사용한다. 해시 테이블의 핵심이다.
성능이 좋은 해시 함수의 특징
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
생일 문제
생일이 같은 사람이 나타날 확률이 50%가 넘으려면 23명만 있으면 된다.
비둘기집 원리
n개의 아이템을 m개의 컨테이너에 넣으려고 할 때, n > m이라면 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어가게 된다.
로드 팩터
해시 테이블에 저장된 데이터의 개수 / 버킷의 개수
로드 팩터 비율에 따라 해시테이블의 크기와 해시 함수의 적당함을 결정한다.
해시 함수
해싱
: 해시 테이블을 인덱싱 하기 위해서 해시 함수를 사용하는 것
충돌
해시에서 충돌은 쉽게 일어난다. 따라서 충돌을 최소화 하는 일은 중요하다. 충돌이 발생하는 경우 처리하는 방법에는 여러가지가 있다.
개별 체이닝
충돌이 발생하면 발생한 곳에 연결리스트로 연결하는 방식이다.
오픈 어드레싱
충돌이 발생하면 빈 공간을 찾아내 저장하는 방식이다. 모든 원소가 자신의 해시값과 일치하는 곳에 저장된다는 보장이 없다.
언어별 해시 테이블 구현 방식
파이썬에서는 딕셔너리가 해시 테이블로 구현되어 있다. 충돌이 발생하면 오픈 어드레싱 방식으로 해결한다.
28. 해시맵 디자인
문제
: 다음의 기능을 제공하는 해시맵을 디자인하라.
-
put(key, value) : 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.
-
get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.
-
remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.
-
예제
입력
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]출력
[null, null, null, 1, -1, null, 1, null, -1]풀이 (개별 체이닝 방식을 이용한 해시 테이블 구현)
class ListNode:
def __init__(self, key = None, value = None):
self.key = key
self.value = value
self.next = None
class MyHashMap:
def __init__(self):
self.size = 1000
self.table = collections.defaultdict(ListNode)
def put(self, key: int, value: int) -> None:
index = key % self.size
# 인덱스에 노드가 없다면 삽입 후 바로 종료
if self.table[index].value is None:
self.table[index] = ListNode(key, value)
return
# 인덱스에 노드가 존재하는 경우에는 연결 리스트로 연결
p = self.table[index]
while p:
# 해당 키를 가진 노드가 이미 존재하면 값만 바꾼다.
if p.key == key:
p.value = value
return
if p.next is None:
break
p = p.next
p.next = ListNode(key, value)
def get(self, key: int) -> int:
index = key % self.size
if self.table[index].value is None:
return -1
# 찾는 노드가 존재할 때 일치하는 키 탐색
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
def remove(self, key: int) -> None:
index = key % self.size
if self.table[index].value is None:
return
# 인덱스의 첫 번 째 노드일 때 삭제 처리
p = self.table[index]
if p.key == key:
self.table[index] = ListNode() if p.next is None else p.next
return
# 연결 리스트 노드 삭제
prev = p
while p:
if p.key == key:
prev.next = p.next
return
prev, p = p, p.next29. 보석과 돌
문제
: J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 대소문자는 구분한다.
- 예제
입력
jewels = "aA", stones = "aAAbbbb"출력
3내 풀이
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
stone_dict = collections.Counter(stones)
count = 0
for je in jewels:
if je in stone_dict:
count += stone_dict[je]
return countif je in stone_dict는 필요 없다. Counter를 사용하면서 없는 것은 0으로 출력되기 때문이다.
풀이 1 (해시 테이블을 이용한 풀이)
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
freqs = {}
count = 0
# 돌(S)의 빈도 수 계산
for char in stones:
if char not in freqs:
freqs[char] = 1
else:
freqs[char] += 1
# 보석(J)의 빈도 수 합산
for char in jewels:
if char in freqs:
count += freqs[char]
return count풀이 2 (defaultdict을 이용한 비교 생략)
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
freqs = collections.defaultdict(int)
count = 0
# 비교없이 돌 빈도 수 계산
for char in stones:
freqs[char] += 1
# 비교없이 보석의 빈도 수 합산
for char in jewels:
count += freqs[char]
return count풀이 3 (Counter로 계산 생략)
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
stone_dict = collections.Counter(stones)
count = 0
for je in jewels:
if je in stone_dict:
count += stone_dict[je]
return count풀이 4 (파이썬다운 방식)
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
return sum(s in jewels for s in stones)30. 중복 문자 없는 가장 긴 부분 문자열
문제
: 중복 문자가 없는 긴 부분 문자열의 길이를 리턴하라.
- 예제 1
입력
s = "abcabcbb"출력
3설명 : 정답은 "abc"로 길이는 3이다.
- 예제 2
입력
s = "bbbbb"출력
1설명 : 정답은 "b"로 길이는 1이다.
- 예제 3
입력
s = "pwwkew"출력
3설명 : 정답은 "wke"로 길이는 3이다. 정답은 반드시 부분 문자열이어야 한다. "pwke"는 서브시퀀스로 연속적이지 않은 문자열이다.
풀이 (슬라이딩 윈도우와 투 포인터로 사이즈 조절)
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = {}
max_length = start = 0
for index, char in enumerate(s):
# 이미 등장했던 문자라면 'start' 위치 갱신
if char in used and start <= used[char]:
start = used[char] + 1
else: # 최대 부분 문자열 길이 갱신
max_length = max(max_length, index - start + 1)
# 현재 문자의 위치 삽입
used[char] = index
return max_length31. 상위 K 빈도 요소
문제
: 상위 k번 이상 등장하는 요소를 추출하라.
- 예제 1
입력
nums = [1,1,1,2,2,3], k = 2출력
[1,2]내 풀이
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
num_dict = collections.Counter(nums)
return_list = []
return_dict = num_dict.most_common(k)
for i in range(k):
return_list.append(return_dict[i][0])
return return_list알아둘 개념
- zip() 함수
: 2개 이상의 시퀀스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀀스로 만들어 준다.
a = [1, 2, 3, 4, 5]
b = [2, 3, 4, 5]
print(zip(a,b))
[(1, 2), (2, 3), (3, 4), (4, 5)]- * (아스테리스트)
: 파이썬에서는 언팩(Unpack)이다. 시퀀스를 풀어헤치는 연산자이다.
fruits = ['lemon', 'pear', 'watermelon', 'tomato']
print(*fruits)
lemon pear watermelon tomato