복습하기5
해시테이블, 보석과 돌, 중복 문자가 없는 가장 긴 부분 문자열, 상위 K 빈도 요소, 비밀번호 찾기, 수 찾기
03/16/2022
해시함수: 어떠한 값이 들어올때 일정한 규칙에따라서 매핑을 하여 고정크기에 넣게 도와주는 함수.
해싱: 해시테이블을 인덱싱하기위해서 함수를 사용하는것.
충돌: 해싱값이 동일하게 나올때. A1 -> ASDF A1 -> ASDF
해시맵디자인
이것을 구현하는 연습을 많이 해야할것같다.
연결리스트, 스택, 큐, 그리고 해시맵디자인 이것을 머리에 익을때까지하자.
#체이닝방식, 해쉬테이블
import collections
class ListNode:
def __init__(self, key = None, value = None):
self.key = key
self.value = value
self.next = None
class MyHashMap:
def __init__(self):
self.size = 1000
self.table = collections.defulatdict(ListNode)
def put(self, key:int, value:int) -> int:
index = key % self.size
if self.table[index].value is None: #만약에 해쉬테이블안에 인덱스값을 가진 값들이 없을때
self.table[index] = ListNode(key, value) #그냥 빈 리스트노드로 저장한다. 존재하지않는 인덱스 나중에 조회할경우 바로 빈 리스트노드 나올것이다.
return
p = self.table[index] #그렇지않고 해쉬테이블안에 인덱스값에 밸류가 있을경우, 노드가 존재하는경우
while p: #p는 인덱스의 첫번째값이고, 계속 탐색한다. p.next를
if p.key == key: #이미 키가 존재할경우, 값을 업데이트하고 빠겨나가는 경우.
p.value = value
return
if p.next is None: #다음노드 없으면 아무것도 하지않고 루프를 빠져나간다.
break
p = p.next
p.next = ListNode(key, value) #여기까지 진행되면 새로운 노드를 생성해줄것이고, 연결할것이다. 이것이 개별체이닝방식.
def get(self, key:int) -> int:
index = key % self.size
if self.table[index].value is None:
return -1 #만약에 해당 인덱스에 아무것도 없으면 이거를 반환한다.
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
def remove(self, key:int) ->None:
index = key % self.sizeif
if self.table[index].value is None:
return
p= self.table[index]
if p.key == key:
self.table[index] = ListNode() if p.next is None else p.next #애초에 self.table[index]
# 이거는 빈 노드이기때문에, 매번 빈 것을 생성하기 때문에 self.table[index]자체를 None으로해버리면 오류발생할것이다
return
#현재노드를 이전과 다음노드로부터 끊어버리기 삭제해야되니까...
prev = p
while p:
if p.key == key:
prev.next = p.next
return
prev, p = p, p.next
보석과 돌
해시 테이블 느낌 도입하면서 풀기.
def numJewelsIsInStones(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(numJewelsIsInStones("aA", "aAAbbbb"))중복 문자가 없는 가장 긴 부분 문자열
투포인터스 사용 start and end. 양쪽이 아니라 왼쪽에서부터 시작.
def lengthOfLongestSubstring(s):
d = {}
res = start = 0
for i, c in enumerate(s):
if c in d and start <= d[c]:
start = d[c] + 1
else:
res = max(res, i - start + 1)
d[c] = i
return res
print(lengthOfLongestSubstring("abcabcbb"))상위k 빈도 요소
굉장히 쉬운문제였지만, 우선순위 큐, 즉 힙을 활용 (heapq모듈)하면 더 효율적이라고한다.
import collections
import heapq
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
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(nums, k))비밀번호 찾기
딕셔너리가 사실 해쉬테이블의 핵심이다 파이썬에서는..그래서쉬운거같네..
import sys
import collections
input = sys.stdin.readline
dic = collections.defaultdict(str)
N, M = map(int,input().split()) # 사이트 수, 비밀번호를 찾을 사이트 수
for i in range(N): # 사이트와 비밀번호 저장
site, passward = map(str, input().split())
dic[site] = passward
for i in range(M): # dic에서 해당 사이트 비밀번호 추출
site = str(input()).rstrip()
print(dic[site])수 찾기
나는 우선 난수를 도입해서 해보았다!!
import sys
import collections
import random
input = sys.stdin.readline
dic = collections.defaultdict(str)
N_number = []
M_number = []
N, M = map(int,input().split())
for i in range(N):
a = random.randrange(1, 100000)
N_number.append(a)
for j in range(M):
b = random.randrange(1, 100000)
M_number.append(b)
for num in M_number:
print(1) if num in N_number else print(0)#이거 식 좋은거같다 알아놓자!파이썬에서 해쉬테이블은 딕셔너리나 마찬가지다. 오늘은 문제들이 그래도 쉽고 괜찮았다. 하지만, 되도록이면 챕터에 맞게 그리고 정답처럼 정석적으로 접근하려고 노력했다. 부족하다아직은..
