11장_해시 테이블

 

 

• 해시 함수 : 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수
• 아무리 좋은 해시 함수라도 충돌은 발생함
  • 개별 체이닝 : 충돌 발생 시 연결 리스트로 연결
  • 오픈 어드레싱 : 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
• 해시 테이블로 구현된 파이썬의 자료형은? : 딕셔너리 (오픈 어드레싱 사용)

 

 

< 보석과 돌 >

1) 해시 테이블을 이용한 풀이

def numJewelInStones(J, S):
    freqs = {}
    count = 0

    for char in S:
        if char not in freqs:
            freqs[char] = 1
        else:
            freqs[char] += 1

    for char in J:
        if char in freqs:
            count += freqs[char]

    return count

print(numJewelInStones("aA", "aAAbbbb"))

 

 

 2) defaultdict를 이용한 비교 생략

 

import collections

def numJewelInStones(J, S):
    freqs = collections.defaultdict(int)
    count = 0

    for char in S:
        freqs[char] += 1

    for char in J:
        count += freqs[char]

    return count

print(numJewelInStones("aA", "aAAbbbb"))

 

 

3) Counter로 계산 생략

 

def numJewelInStones(J, S):
    freqs = collections.Counter(S)
    count = 0

    for char in J:
        count += freqs[char]

    return count

print(numJewelInStones("aA", "aAAbbbb"))

 

 

4) 파이썬다운 방식

 

def numJewelInStones(J, S):
    return sum(s in J for s in S)

print(numJewelInStones("aA", "aAAbbbb"))

 

 

 

< 중복 문자 없는 가장 긴 부분 문자열 >

1) 슬라이딩 윈도우와 투 포인터로 사이즈 조절

 

def lengthOfLongestSubstring(s):
    used = {}
    max_length = start = 0
    for index, char in enumerate(s):
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_length = max(max_length, index - start + 1)
        
        used[char] = index
    
    return max_length

print(lengthOfLongestSubstring("abcabcbb"))

 

 

< 상위 K 빈도 요소 >

1) Counter를 이용한 음수 순 추출

 

def topKFrequent(nums, k):
    freqs = collections.Counter(nums)
    freqs_heap = []

    for f in freqs:
        heapq.heappush(freqs_heap, (-freqs[f], f))

    topk = list()

    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

print(topKFrequent([1, 1, 1, 2, 2, 3], 2))

 

 

2) 파이썬다운 방식

 

def topKFrequent(nums, k):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

print(topKFrequent([1, 1, 1, 2, 2, 3], 2))

 

 

 

< zip() 함수 >

 

• 2개 이상의 시퀀스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀀스를 만듦
• zip() 결과 자체는 리스트가 아닌 튜플을 만들기에 값 변경 불가능
• 실제값 출력 위해서는 list()로 묶어주기

>>> a = [1, 2, 3, 4, 5]
>>> b = [2, 3, 4, 5]
>>> c = [3, 4, 5]
>>> list(zip(a, b, c))
[(1, 2, 3), (2, 3, 4), (3, 4, 5)]

 

 

< 아스테리스크 (*) >

 

• 언팩. 시퀀스를 풀어 헤치는 연산자

>>> fruits = ['lemon', 'pear', 'watermelon', 'tomato']
>>> print(fruits)
['lemon', 'pear', 'watermelon', 'tomato']

>>> print(*fruits)
lemon pear watermelon tomato

>>> a, *b = [1, 2, 3, 4]
>>> print(a)
1
>>> print(b)
[2, 3, 4]

>>> *a, b = [1, 2, 3, 4]
>>> print(a)
[1, 2, 3]
>>> print(b)
4

 

• 파이썬에서 * 1개는 튜플과 리스트의 시퀀스 언패킹
• ** 2개는 키/값 페어 언패킹

>>> date_info = {'year' : '2020', 'month' : '01', 'day' : '7'}
>>> new_info = {**date_info, 'day' : '14'}
>>> new_info
{'year' : '2020', 'month' : '01', 'day' : '14'}