문제
현수는 영어로 시는 쓰는 것을 좋아합니다.
현수는 시를 쓰기 전에 시에 쓰일 단어를 미리 노트에 적어둡니다.
이번에는 N개의 단어를 노트에 적었는데 시에 쓰지 않은 단어가 하나 있다고 합니다. 여러분이 찾아 주세요.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=100)이 주어진다.
두 번째 줄부터 노트에 미리 적어놓은 N개의 단어가 주어지고, 이어 바로 다음 줄부터 시에 쓰인 N-1개의 단어가 주어진다.
▣ 출력설명
첫 번째 줄에 시에 쓰지 않은 한 개의 단어를 출력한다.
입력예제1
5
big
good
sky
blue
mouse
sky
good
mouse
big
출력예제1
blue
[내 코드]
N=int(input())
hash={}
for i in range(N):
word=input()
hash[word]=1
for i in range(N-1):
word=input()
hash[word]=0
print(hash)
for word in hash:
if hash[word]==1:
print(word)[해설코드]
n=int(input())
p=dic()
for i in range(n):
word=input()
p[word]=1
for i in range(n-1):
word=input()
p[word]=0
for key,val in p.items():
if val==1:
print(key)
break
[설명]
해시 테이블
해시 테이블이란 해시함수를 사용하여 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조. 해시 테이블은 key와 value가 1:1매핑되어있기 때문에 평균적으로 모든 작업이 O(1)의 상수형 시간복잡도를 가진다. 이떄, 해시테이블은 두 개이상의 value가 다른 데이터임에도 불구하고 같은 key값을 가지는 경우 해시충돌이 발생한다.
[해시충돌 방법]
1.오픈 해싱
해시 값이 중복되는 경우에 먼저 저장된 데이터에 linked list를 이용하여 중복 해시데이터를 연결해준다. 파이썬에서는 이중 리스트 구조를 활용한다.
2. 클로즈 해싱
해시 중복이 발생할 시에 해당 해시 값부터 순차적으로 빈 공간을 찾는다.가장 처음 찾는 빈 공간에 key와 value를 저장한다.
