[3부 선형 자료구조] 11장 해시 테이블

📌 28) 해시맵 디자인 ( 리트코드 706. Design HashMap )

✔ 풀이

class ListNode: #연결리스트 노드 클래스
    def __init__(self, key = None, value = None):
        self.key = key
        self.value = value
        self.next = None
        
from collections import defaultdict
class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.table = defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        idx = key % self.size
        
        #해당키를 해싱한 인덱스가 존재하지 않을경우
        if self.table[idx].value is None:
            self.table[idx] = ListNode(key, value)
            return
            
        #존재할 경우 key값이 같으면 정보를 업데이트 하고, 키 값이 없으면 새로 추가해줌
        p = self.table[idx] #첫번째 인덱스 가리킴
        while p:
            if p.key == key: #정보 업데이트
                p.value = value
                return
            if p.next is None: #마지막 인덱스일 경우
                break
            p = p.next #p다음으로 이동
        p.next = ListNode(key, value) #새로운 노드 추가
        

    def get(self, key: int) -> int:
        idx = key % self.size
        
        #해당키를 해싱한 인덱스가 존재하지 않을경우
        if self.table[idx].value is None:
            return -1
        
        p = self.table[idx]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1
        

    def remove(self, key: int) -> None:
        idx = key % self.size
        
        #해당키를 해싱한 인덱스가 존재하지 않을경우
        if self.table[idx].value is None:
            return
        
        #첫번째 노드가 삭제할 노드일 경우
        p = self.table[idx]
        if p.key == key:
            #노드가 유일할 경우 ListNode()로 값 변경
            #뒤에 연결 된 노드가 있을경우 다음노드(p.next)로 값 변경
            self.table[idx] = ListNode() if p.next == None else p.next
            return
        
        #첫번째 노드가 삭제할 노드가 아닐경우
        prev = p 
        while p:
            if p.key == key:
                prev.next = p.next
                return 
            prev, p = p, p.next
        

📌 29) 보석과 돌 ( 리트코드 771. Jewels and Stones )

✔ 풀이 (해시 테이블을 이용한 풀이)

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        
        stone_dic = {}
        for char in stones:
            if char not in stone_dic:
                stone_dic[char] = 1
            else:
                stone_dic[char] += 1
        
        cnt = 0
        for char in jewels:
            if char in stone_dic:
                cnt += stone_dic[char]
                
        return cnt

✔ 풀이 (defaultdict을 이용한 비교 생략)

from collections import defaultdict
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stone_dic = defaultdict(int)
        for char in stones:
            stone_dic[char] += 1
        
        cnt = 0
        for char in jewels:
            cnt += stone_dic[char]
        
        return cnt

✔ 풀이 (Counter로 계산 생략)

from collections import Counter
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stone_dic = Counter(stones)
        
        #Counter은 존재하지 않는 키의 경우 KeyError발생하는게 아닌 0을 출력해줌
        #->defaultdict과 마찬가지로 에러에대한 예외처리 할 필요X
        cnt = 0 
        for char in jewels:
            cnt += stone_dic[char]
            
        return cnt

✔ 풀이 (Pythonic Way)

from collections import Counter
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum([s in jewels for s in stones])

📌 30) 중복 문자 없는 가장 긴 부분 문자열 ( 리트코드 3. Longest Substring Without Repeating Characters )

✔ 풀이 (리스트)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        answer, prev = 0, []
        for char in s:
            if char in prev:
                answer = max(answer, len(prev))
                prev = prev[prev.index(char) + 1: ] + [char]
            else:
                prev.append(char)

        return max(answer, len(prev))

✔ 풀이 (슬라이딩 윈도우 & 투 포인터)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        used = {}
        start = max_len = 0
        for i, char in enumerate(s):
            if char in used and start <= used[char]: #중복 된 문자열일 경우
                start = used[char] + 1
            else:
                max_len = max(max_len, i - start + 1)
            
            #문자char의 위치를 최근위치 i로 갱신
            used[char] = i

        return max_len

📌 31) 상위 K 빈도 요소 ( 리트코드 347. Top K Frequent Elements )

✔ 풀이 (Counter & heapq)

from collections import Counter
import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_dic = Counter(nums)
        
        #힙에 값 추가
        freqs_heap = []
        for key in num_dic:
            heapq.heappush(freqs_heap, (-num_dic[key], key))
            
        topk = []
        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])
            
        return topk

✔ 풀이 (Pythonic Way - Counter, most_common메서드)

#most_common(k) = > 상위 k개의 요소를 보여줌
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [ key for key, val in Counter(nums).most_common(k)]