[python] Hash와 Dictionary - 프로그래머스 커뮤러닝 week1

1. Before Class

• 선행 문제인 '완주하지 못한 선수'를 풀어보면서 참여/완주 리스트를 비교하였고, 중복값이 있을 경우 해시함수를 사용한다는 것을 배움.

2. During Class

(1) Hash의 배경

• 위 문제에서 이름목록 대신 번호가 주어졌다면, 이를 '선형 배열(linear array)'라고 부를 수 있다.
• 번호 외에 문자열 등에 접근할 수 있는 좋은 자료구조가 필요했다.

(2) Hash의 개념

• key값과 hash table로 구성되어 있다.
• hash table은 hash bucket들로 구성되어 있으며, hash bucket에 value가 담겨있다.

(3) Dictionary와의 비교

• 해시테이블 클래스는 Dictionary 클래스의 해시 구현이다.
• 해싱은 자료구조에서 특정 값을 가장 신속하게 찾는 방법이다.
• 해시함수는 어떤 키에 해당하는 값의 주소를 테이블에서 찾아주는 함수이다.(조회속도 빠름)

3. After Class

예제: 완주하지 못한 선수

def solution(participant, completion):
    answer = '' 
    athlete = 0 # 완주자를 분류하여 넣을 변수
    dict = {} # 해시를 구현할 딕셔너리
    for i in participant:
        dict[hash(i)] = i # 참여자명단을 순회하며 해시 변환 + 딕셔너리에 할당
        athlete += int(hash(i)) # 정수형으로 athlete 변수에 할당
    for j in completion:
        athlete -= hash(j) # 완주자명단을 순회하며 참여자명단에서 해시 삭제
    answer = dict[athlete] # 완주자를 제외한 변수의 딕셔너리화 (해시적 구현 해제)
    return answer # 미완주자 이름이 들어있는 딕셔너리 반환