[python 기초] 백준: 17219번 / hash table

📍 In a nutshell

• hash table: key를 value에 맵핑할 수 있는 자료구조
  • 즉, hash 함수를 통해 key를 hash값으로 매핑하고, hash값을 주소(index)로 삼아 value를 key와 함께 저장하는 것
• 핵심은 hash 함수
  • 임의의 데이터를 고정 크기 값으로 매핑하는 데 사용하는 함수
  • 쉽고 빠른 검색을 위해 사용되는 기법으로, 성능이 좋을 수록 쉽고 빠르며 해시 함수 값 충돌이 최소화된다
    (충돌: hash함수를 거쳤을 때, 2개의 key가 같은 해시함수 값을 가리키는 것)
• 파이썬의 dictionary는 hash table로 구현된 자료형이다
  • 파이썬은 해시값 충돌 시 오픈 어드레싱 방식을 사용한다
  • 자바는 개별 체이닝 사용한다
    

    이미지 출처: https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

문제)
첫째 줄에 저장된 사이트 주소의 수 N과 비밀번호를 찾으려는 사이트 주소의 수 M이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다.

N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.

풀이)
사이트 주소와 비밀번호를 dictionary 형태로 만들어야, key를 통해 value를 바로 찾을 수 있다.

N, M = map(int, input().split())
myDict = {}

for _ in range(N):
    host, pw = map(str, input().split())
    myDict[host]  = pw

for _ in range(M):
    search_host = input()
    print(myDict[search_host])

• 사이트 주소 총 개수 N과 비밀번호를 검색할 사이트 주소 개수 M을 입력한다
• 첫 번째 for문을 통해 입력받은 host와 pw를 저장한다
  • return값은 따로 없으므로, _를 사용
  • 입력받으면 key:value 형태로 myDict에 저장
• 두 번째 for문
  • return값은 따로 없으므로, _를 사용
  • 검색할 host를 입력하면 해당 value를 print

Additional) 충돌 - 생일 문제
값의 충돌은 생각보다 쉽게 일어나는데, 이를 알 수 있는 대표적인 문제가 '생일 문제'.
생일 문제의 point는, 23명만 모여도 생일이 같은 2명이 모일 확률이 50%를 넘는다는 것이다.

아래와 같이 1만번을 시도했을 때, 같은 생일이 나올 확률은 최소 50%임이 증명된다.

import random

TRIAL = 10000
same_birthday = 0 

for _ in range(TRIAL):

	birthdays = []    
    #365일 중 각자의 생일을 random으로 지정 - 총 23명
    #생일이 같으면, same_birthday를 1씩 카운트 
    for _ in range(23):
    	birthday = random.randint(1,365)
        if birthday in birthdays:
        	same_birthday += 1
            break 
        birthdays.append(birthday)
        
result = (same_birthday/TRIAL)*100 

print(f'생일이 같을 확률은: {result}% 입니다!')
    	

참고 자료
<파이썬 알고리즘 인터뷰>, 박상길
https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94
https://youtu.be/HraOg7W3VAM