[항해99] HashTable

HashTable

hash 함수

임의크기 데이터를 고정크기 값으로 매핑하는데 사용

해싱은 가능한 빠르게 저장하고 검색하기위해 사용하는 기법 중 하나.
파이썬의 set 이나 딕셔너리가 이를 활용한 자료구조.
그래서 시간복잡도가 O(1)임!! <- 이게 진짜 중요해.

 

보석과 돌

https://leetcode.com/problems/jewels-and-stones/

Jewels and Stones - LeetCode

딕셔너리를 이용해서 풀 수 있는 간단한 구현 문제.

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

중복문자 없는 가장 긴 substring

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

아무래도 제일 난이도가 있던 문제.

포인터 두개를 가지고 시작해서 index, start의 위치를 가지고 슬라이딩 윈도우 기법으로 미끄러져나가며 확인한다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {} # 순차적으로 지나가면서 넣은 딕셔너리
        max_length = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]: # 만약에 다음으로 올값이 이미 used딕셔너리에 있고, 해당 값이 시작하는 위치보다 높다면
                start = used[char] + 1 # 시작 하는 위치를 해당 value값보다 높여준다. 그러면 그전에 사용한 변수들 값과는 상관이 없어진다
            else:
                max_length = max(max_length, index - start +1) # 기존의 길이보다 높으면 두번째 매개변수가 그렇지 않으면 기존의 max_length가 유지
            used[char] = index # 값과 index값을 저장
        return max_length

상위 K 빈도 요소

https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

딕셔너리를 소팅하는 법을 안다면 쉽게 풀리는 문제.

class Solution:
    def topKFrequent(self, nums: List[int], k: int):
        d = dict(Counter(nums))
        d = dict(sorted(d.items(), key = lambda item: item[1], reverse = True))
        return list(d)[:k]

파이썬 콜렉션 중에 Counter의 most_common을 이용해도 쉽게 풀 수 있다.

most_common(k)는 카운터가 센 key value에서 ( 어떤숫자가 , 몇 개 있는지) value 가 가장 높은 k개의 원소를 리스트로 리턴하는 함수. 

리턴 값은 딕셔너리의 key value의 tuple 형태가 원소인 리스트.

from typing import List, Counter


class Solution:
    def topKFrequent(self, nums: List[int], k: int):
        d = Counter(nums).most_common(k)
        ans = []
        for i in d:
            ans.append(i[0])
        return ans

수 찾기 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

이게 뭐라고 정답률이 20퍼지? 하고 단순하게 접근했다가 나도 20퍼단에 들어간 문제.

처 - 참

시간초과의 문제는 알고리즘의 시간 복잡도를 잘 생각하도록 하자.

리스트는 일반적으로 찾을 때 O(n) 의 시간 복잡도를 가지는 데 반해, 해시맵은 ( 파이썬의 경우 set이나 dict ) O(1)의 시간복잡도를 가져서, 복잡도를 한 차원 낮추어 주는 효과가 있다.

N = int(input())
# s = list(map(int, input().split())) -> 이걸로 하면 O(n) 의 시간복잡도로 순회를 돌아서 
s = set(map(int, input().split()))
M = int(input())
lst2 = list(map(int, input().split()))
for i in lst2: # 여기서 O(n^2) 의 시간복잡도가 되어서 시간초과가 난다.
    if i in s:
        # set은 hashtable으로 만들었다고 일단 생각한다면, 해시테이블에선 시간복잡도가 O(1)이 탐색시간이라서
        print(1)
    else:
        print(0)

비밀번호 찾기

https://www.acmicpc.net/problem/17219

17219번: 비밀번호 찾기

마찬가지로 문제 자체가 어렵다기보다는, 시간복잡도를 잘 생각해야 하는 문제.

입력데이터의 값이 아주 많아질 때 해시테이블이 꼭 필요하다고 강조해주는 문제다.

N, M = map(int, input().split())
d = {}

for _ in range(N):
    site, pw = input().split()
    d[site] = pw

for _ in range(M):
    site = input()
    print(d[site])