백준 1764 듣보잡 파이썬
스타트링크 (Startlink)
1764번 : 듣보잡
알고리즘 : 집합, 이진탐색, 해시 테이블
정답 코드
코드 1 (집합)
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = {input() for _ in range(n)}
b = {input() for _ in range(m)}
result = sorted(list(a & b))
print(len(result))
for i in result:
print(i.strip())코드 2 (이진 탐색)
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = [None] * n
b = [None] * m
result = []
if n < m:
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
else:
a = [input() for _ in range(m)]
b = [input() for _ in range(n)]
b.sort()
n, m = len(a), len(b)
for word in a:
pl, pr = 0, m - 1
while pl <= pr:
mid = (pl + pr) // 2
if word == b[mid]:
result.append(word)
break
elif word < b[mid]:
pr = mid - 1
else:
pl = mid + 1
result.sort()
print(len(result))
for i in result:
print(i.strip())코드 3(해시 테이블)
from typing import Any
import hashlib, sys
input = sys.stdin.readline
class Node:
def __init__(self, value: Any, next: None) -> None:
self.value = value
self.next = next
class ChainedHash:
def __init__(self, cap: int) -> None:
self.cap = cap
self.table = [None] * cap
def hash_value(self, value:Any) -> int:
if isinstance(value, int):
return value % self.cap
return(int(hashlib.sha256(str(value).encode()).hexdigest(), 16) % self.cap)
def add(self, value: Any) -> None:
hash = self.hash_value(value)
self.table[hash] = Node(value, self.table[hash])
def search(self, value: Any) -> bool:
hash = self.hash_value(value)
p = self.table[hash]
while p is not None:
if p.value == value:
return True
p = p.next
return False
n, m = list(map(int, input().split()))
table = ChainedHash(100000)
result = []
if n > m:
for _ in range(n):
table.add(input())
a = [None] * m
a = [input() for _ in range(m)]
else:
for _ in range(m):
table.add(input())
a = [None] * n
a = [input() for _ in range(n)]
for i in a:
if table.search(i):
result.append(i)
result.sort()
print(len(result))
for i in result:
print(i.strip())해설
해당 문제는 집합을 이용하면 매우 쉽고 빠르게 풀 수 있습니다.
이번 포스트에서는 집합뿐만 아니라 이진탐색, 해시를 사용한 자료구조를 통해 문제를 풀고 효율성을 비교 해보겠습니다.
1. 집합
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = {input() for _ in range(n)}
b = {input() for _ in range(m)}
result = sorted(list(a & b))
print(len(result))
for i in result:
print(i.strip())집합 a에 듣도 못한 사람, 집합 b에 보도 못한 사람을 입력 받은 후,
집합a 와, 집합 b의교집합 연산(&)를 통해 듣도보도못한사람을 구합니다.
집합 방식을 사용한 코드는 60ms 걸렸습니다.
2. 이진탐색
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
a = [None] * n
b = [None] * m
result = []
if n < m:
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
else:
a = [input() for _ in range(m)]
b = [input() for _ in range(n)]
b.sort()
n, m = len(a), len(b)
for word in a:
pl, pr = 0, m - 1
while pl <= pr:
mid = (pl + pr) // 2
if word == b[mid]:
result.append(word)
break
elif word < b[mid]:
pr = mid - 1
else:
pl = mid + 1
result.sort()
print(len(result))
for i in result:
print(i.strip())검색 횟수를 줄이기 위해 듣도 못한 사람의 리스트와 보도 못한 사람의 리스트중
작은 리스트를 a, 큰 리스트를 b 라고 하고, b에서 a의 요소를 검색하겠습니다.
이진 탐색을 사용하기 위해 b를 정렬하고 왼쪽 포인터를 pl, 오른쪽 포인터를 pr로 두었습니다.
이진탐색을 사용한 코드는 360ms 걸렸습니다.
3. 해시법
from typing import Any
import hashlib, sys
input = sys.stdin.readline
class Node:
def __init__(self, value: Any, next: None) -> None:
self.value = value
self.next = next
class ChainedHash:
def __init__(self, cap: int) -> None:
self.cap = cap
self.table = [None] * cap
def hash_value(self, value:Any) -> int:
if isinstance(value, int):
return value % self.cap
return(int(hashlib.sha256(str(value).encode()).hexdigest(), 16) % self.cap)
def add(self, value: Any) -> None:
hash = self.hash_value(value)
self.table[hash] = Node(value, self.table[hash])
def search(self, value: Any) -> bool:
hash = self.hash_value(value)
p = self.table[hash]
while p is not None:
if p.value == value:
return True
p = p.next
return False
n, m = list(map(int, input().split()))
table = ChainedHash(100000)
result = []
if n > m:
for _ in range(n):
table.add(input())
a = [None] * m
a = [input() for _ in range(m)]
else:
for _ in range(m):
table.add(input())
a = [None] * n
a = [input() for _ in range(n)]
for i in a:
if table.search(i):
result.append(i)
result.sort()
print(len(result))
for i in result:
print(i.strip())set 자료형의 시간복잡도는 검색(x in s)의 경우 O(1), 교집합(s & t)의 경우
O(min(s, t))로 매우 작습니다. 이는 set내부 구조가 해시테이블 구조로 이루어져 있기 때문입니다.
해시테이블을 직접 구현하여 문제를 풀어보겠습니다.
Node 클래스의 value에 값을, next에 다음 노드를 담습니다.
ChainedHash클래스에서 해시테이블의 생성, 추가, 검색을 담당합니다
__init__ 함수는 설정한 크기의 해시 테이블을 생성합니다.
add 함수는 해시테이블에 값을 추가합니다. 해시값이 같을 경우 node를 제일 앞에 추가하고 뒤에 기존 node들을 연결합니다.
중복되는 이름이 없다 하였으므로 중복 검사는 하지 않겠습니다.
search함수는 해시테이블에서 값을 찾습니다.
해시값이 같은 노드를 해시테이블에서 찾고, 연결된 노드를 확인하며 value가 동일한지 확인합니다.
value를 찾았다면 True, 못 찾았다면 False를 반환합니다.
해시법을 사용한 코드는 해시테이블의 크기에 따라 실행 속도가 달랐습니다.
해시테이블의 크기가 100인 경우 4496ms,
해시테이블의 크기가 1000인 경우 520ms,
해시테이블의 크기가 10000인 경우 336ms,
해시테이블의 크기가 100000인 경우 284ms,
해시테이블의 크기가 500000인 경우 280ms
해시 테이블을 직접 구현했음에도 set자료형보다 느린 이유는
CPython 특성상 set이 C언어로 구현되어 Python으로 구현하는 것 보다 효율적이기 때문입니다.