해시 함수란?
해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수.
즉 , ABC , 1245BC , AF32B 가 있어도 해시 함수를 통해 2바이트의 고정 크기 값으로 매핑 실킬 수 있다.
해시 함수에는 저장 방법에 따라 2가지 방식으로 나눌 수 있다.
- 개별 체이닝 방식과 오픈 어드레싱 방식
- 개별 체이닝 방식은 충돌 발생시 연결 리스트를 통해 연결하는 방식.
- 오픈 어드레싱은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식.
- C++ 와 자바는 개별 체이닝 방식이고, python은 오픈 어드레싱 방식이다.
- "해시 테이블로 구현된 파이썬의 자료형은?" 바로 딕셔너리이다.
문제 1. 해시맵 디자인
다음의 기능을 제공하는 해시맵을 디자인하라.
- put(key,value) : 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.
- get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.
- remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.
개별 체이닝 방식으로 해시 테이블 구현
class ListNode:
def __init__(self, key=None, value = None):
self.key = key
self.val = value
self.next = None
class MyHashMap:
# 초기화
def __init__(self):
self.size = 1000
self.table = collections.defaultdict(ListNode)
# 삽입
def put(self,key):
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 in None:
break
p= p.next
p.next = ListNode(key,value)
# 조회
def get(self,key):
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):
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 , next- 기본 초기화 설정부터 , 조회 , 삽입 ,삭제 순으로 메서드가 정리되어있다.
- defaultdict 은 존재하지 않는 인덱스로 조회를 할 경우, 에러를 내지 않고 바로 디폴트 객체를 만들어 준다.
- 해당 인덱스에 노드가 존재하는 경우는 충돌하는 경우를 말한다.
2. 보석과 돌
J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 대소문자는 구분한다.
- ex) 입력이 J="aA" , S = "aAAbbbb" 라면 3이 출력된다.
해시 테이블을 이용한 풀이
def numJewelsInStones(self, J,S):
freqs = {}
count = 0
# 돌(S)의 빈도 수 계산
for char in S:
if char not in freqs:
freqs[char] = 1
else:
freqs[char] += 1
# 보석(J)의 빈도 수 합산
for char in J:
if char in freqs:
count += freqs[char]
return count- J 라는 해시테이블을 만들고 , 돌의 빈도수를 계산한다.
- 돌의 빈도수는 for 문을 통해 원소의 개수를 해시테이블에 계산하는 방식이다.
- 그리고 보석만의 빈도 수를 더해주면 된다.
defaultdict를 이용한 비교 생략
def numJewelsInStones(self, J,S):
freqs = collections.defaultdict(int)
count = 0
# 비교 없이 돌(S)의 빈도 수 계산
for char in S:
freqs[char] +=1
# 비교 없이 보석(J)의 빈도 수 합산
for char in J:
count += freqs[char]
return count- defaultdict을 이용하면 사전에 값이 없는 경우 자동으로 디폴트 (0) 의 값이 설정된다.
- 코드가 깔끔해진다.
Counter로 계산 생략
def numJewelsInStones(self, J,S):
freqs = collections.Counter(S) #돌 빈도 수 계산
count = 0
for char in J:
count += freqs[char]
return count- collections.Counster() 를 사용하면 개수 계산을 손쉽고 빠르게 진행할 수 있다.
파이썬 다운 방식
def numJewelsInStones(self, J,S):
return sum(s in J for s in S)- 리스트 컴프리헨션으로 한 줄의 코드로 풀이가 가능하다.
- [s for s in S] 는 각 문자를 리스트화 시킨 것을 의미하고, [ s in J for s in S ] 는 각 문자를 하나씩 출력하고 J에 들어 있는지 여부를 True 혹은 False로 출력해주는 리스트 컴프리헨션이다.
Univ of Seoul , Statistics