#1. 해시테이블 (hash) / python dictionary

정의

빠른 탐색을 위해 key-vlaue 쌍을 저장하는 자료구조이며 key는 중복될 수 없고 순서가 없다.

파이썬에서는 dictionary 데이터 타입이 해시테이블을 제공한다.

 

*코드 예시

student = {
	1 : "최하나",
    2 : "최두리",
    3 : "최세찌",
    4 : "최네찌"
    
}

해시테이블은 저장, 삭제, 검색 모두 O(1)의 시간복잡도를 가져 매우 빠르다.

 

In 연산자와 사용

특정 key값이 해시테이블에 있는지 조회할 때 in과 사용하면 매우 효율적이다. (리스트는 O(n) 인데, 해시테이블은 O(1) 시간복잡도를 가짐)

만약에 1000명의 학생중에 "최하나" 라는 학생이 있는지가 궁금하다고 할 때 students = ['김xx' , '이xx', ....., '최xx'] 이렇게 리스트로 정의해두고 "최하나" in students 로 구현하면 최악의 경우 1000번 찾아보게되어 O(N)의 시간복잡도를 가진다.

이걸 딕셔너리로 구현해서

students = {

 "김xx": True,

 "이xx": True,

...

 "최xx": True

}

 

 "최하나" In students 로 찾으면 해당 딕셔너리에 key값이 있을 경우 O(1)의 시간복잡도로 True를 반환하고 아닐경우 False를 반환한다.

 

관련 함수들

1) dictionary.items(): key와 value에 모두 접근

2) dictionary.keys() : key에 접근

3) dictionary.values() : value에 접근 

4) dictionary.get(): key에 대한 value 추출

*students.get(20230101) -> "김xx"

없는 값을 key로 넣었을 때 default로 none 반환하며, default값을 지정해줄 수 있음

*studnets.get(20230101,"최하나") -> 20230101로 조회하고 없을 경우 최하나 리턴

문제풀이

유형1. 프로그래머스: 포켓몬 (lv1)  :빈도수 계산

프로그래머스

파이썬 collections 클래스의 Counter 함수를 사용해서 리스트에 담긴 포켓몬을 종류별로 몇개씩 있는지 딕셔너리 형태로 변경

일단 전체 포켓몬의 절반만 가져가라고 했기때문에 모든 포켓몬의 종류가 다를때에도 max로 전체의 1/2개 종류의 포켓몬을 가져갈 수 있다. (max_num)

만약에 중복된 포켓몬의 종류가 많을 경우에 counter의 key값의 종류가 적어진다. 예를들어 입력이 [1,1,1,1,1,1] 일경우 

Counter({'1':6}) 의 딕셔너리를 가지며 크기는 1이다. 이때 가져갈 수 있는 포켓몬의 종류는 1가지이다. 

따라서 이 중복값을 고려한 크기와 , 최대로 가져갈 수 있는 포켓몬의 수를 비교해서 결과 리턴 

from collections import Counter
def solution(nums):
    num = len(Counter(nums))
    max_num = len(nums)/2
    return max_num if max_num <num else num

* 다른사람들 풀이를 보니 set을 사용해서 중복을 줄여서 비교하는 방법 사용 -> set도 값만 저장하지만 내부적으로 해시테이블로 저장해서 딕셔너리와 같은 효율을 가진다고 함

 

유형2. 프로그래머스 전화번호 :특정 문자열로 시작하는 값, 리스트에서 찾기> 리스트를 딕셔너리로 변환하기

프로그래머스

def solution(phone_book):
    phone_book = sorted(phone_book)
    phone_dict = {phone: 1 for phone in phone_book} #딕셔너리로 변환 
    for phone in phone_book:
        temp=''
        for num in phone:
            temp += num
            #해시테이블에서 검색하는 부분!
            if temp in phone_dict and temp != phone:
                return False 
    return True

phone_dict = {"119": 1 , "2039123":1, "4576323":1} 이런식으로 value를 모두 1로 넣어준 dictionary로 찾으려고 하는 값을 모두 key로 지정해주는 방법