[Python3 코딩테스트(4)] Hash Table

Hash Table

효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value 쌍의 데이터를 입력

Hash Function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장

출처: 개발남노씨 인프런 강의

저장, 삭제, 검색의 시간복잡도 : O(1)

왜 Hash Table을 활용하는가?

HashFunction을 통해 key 값을 가공해서 해당 hash 값을 index 값으로 결정할 수 있기 때문에 사용함.

BUT, 문제가 있음. → Collision 문제

• Open Addressing: 충돌이 발생한 index의 다음 index에 저장하는 것
• Chaining

Python에서는 Hash Table을 Dictionary를 통해 구현한다.

• key값은 유일
• Dictionary를 활용함으로써 시간복잡도를 획기적으로 줄일 수 있다.(But, 딕셔너리를 새로 선언해서 값을 넣어야 하기 때문에 메모리는 상대적으로 많이 쓰임)
• 특히 key in {dic} 구조가 핵심

score = {
    'math': 97
    'sci': 81
    'eng': 100
}

#시간복잡도 O(1)
print(score['math'] in score) #True

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

딕셔너리를 활용해서 시간복잡도를 획기적으로 줄이자

def two_sum(nums, target):
    #시간복잡도 O(n)    
    dict={}
        for i,n in enumerate(nums):
            if n in dict:
                return dict[n],i
            else:
                dict[target-n]=i

https://leetcode.com/problems/longest-consecutive-sequence/

Longest Consecutive Sequence - LeetCode

 

Hash 기본 함수

from collections import Counter

def solution(participant, completion):
    #for문으로 푸는 건 10^5명 이하라는 제약조건 때문에 안됨
    #그렇다면 갯수로 비교해야 할 것 같긴한데..
    
    # Dictionary
    # 키를 통해 값을 도출한다.
    # dict[key]=value

    # 키에 값을 대입하며 키가 존재하지않을때 값의 선언을 동시에 진행한다.
    # dict[key]=dict.get(value,'default')

    # value,key값으로 자유롭게 정리한 값들을 정렬한다.
    # dict=sorted(dict,key=lambda x:x[k])
    
    # 데이터의 개수를 셀 때 매우 유용한 파이썬의 collections 모듈의 Counter 클래스
    dict_p = Counter(participant)
    dict_c = Counter(completion)
    ans = ''
    
    for pname in dict_p:
        if dict_p[pname] != dict_c[pname]:
            ans = pname

    return ans

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스