해시 - 몸풀기 문제

문제18 두개의 수로 특정값 만들기

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True 없으면 False를 반환

내가 처음에 생각한 아이디어 : arr을 딕셔너리로 만들고 for문 두개로 탐색해서 dic[i]+dic[j]==target있는지 확인 -> for문 두개이니 시간 초과

def has_two_sum(arr,target):
	dic={i:arr[i] for i in range(len(arr))}
    for i in range(len(arr)):
		for j in range(i+1,len(arr)):
        	if dic[i]+dic[j]==target:
            	return True
    return False
        	

책에 있는 아이디어 : 임의의 원소 x에 대해 x+k=target이 되는 k가 배열에 있는지?

def count_sort(arr,k):
	hashtable=[0]*(k+1)
    
    for num in arr:
    	if num<=k:
        	hashtable[num]=1
	return hashtable

def solution(arr,target):
	hashtable=count_sort(arr,target)
	for num in arr:
    	complemet=taget-num
        if (
        	complement!=num
            and complemet>=0
            and complement<=target
            and hashtable[complement]==1
        ):
        	return True
    return False 

시간 복잡도는 해시테이블을 초기화할 때 O(K), arr을 순회할 때 O(N)

내가 해시테이블을 만든다 ! 라고 생각하면 된다

문제 19 문자열 해싱을 이용한 검색 함수 만들기

문자열 리스트 string_list와 쿼리 리스트 query_list가 있을 때 각 쿼리 리스트에 있는 문자열이 string_list에 있는지 여부를 확인
문자열이 있으면 True, 없으면 False, 문자열의 존재 여부는 리스트 형태로 반환

hash(s)=(s[0]+s[1]p+s[2]p2+ ... +s[n-1]p(n-1)) mod m를 활용해서 해싱 함수 구현

시간복잡도 : O(N+K)

def polynominal_hash(str):
	p=31 # 소수
    m=1_000_000_007 # 버킷크기
    hash_value=0
    for char in str:
    hash_value=(hash_value*p +ord(char))%m
return hash_value

def solution(string_list,query_list):
	hash_list=[polynominal_hash(str) for str in string_list]
    result=[]
    for query in query_list:
    	query_hash=polynominal_hash(query)
        if query_hash in hash_list:
        	result.append(True)
        else:
        	result.append(False)
    return result

cf ) ord()로 아스키코드 값 얻음