[Baekjoon] 14425번 : 문자열 집합 (Python, 문자열, 해시)

[Baekjoon] 14425번 : 문자열 집합 (Python, 문자열, 해시)

 

목차

 

 

 

 

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

14425번: 문자열 집합

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 35488KB / 시간 3756ms / 코드 길이 210B

 

n개의 입력(집합 S), m개의 입력이 별도로 주어지고 m개의 입력에 대하여 집합 S에 있는지 판별하는 코드를 작성해야 한다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
ns = [input().rstrip() for _ in range(n)]

cnt = 0
for i in range(m):
    t = input().rstrip()
    if t in ns:
        cnt += 1

print(cnt)

 

방법 2 - 메모리 35784KB / 시간 164ms / 코드 길이 235B

 

dict는 해시이므로 훨신 빠르다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
d = dict()
cnt = 0
for _ in range(n):
    s = input().rstrip()
    d[s] = 1

for i in range(m):
    t = input().rstrip()
    if t in d:
        cnt += 1

print(cnt)

 

 

방법 3 - 메모리 36140KB / 시간 144ms / 코드 길이 213B

 

set 역시 dict만큼 빠르다. list가 가장 느리다.

물론 그만큼 메모리 사용이 늘어남

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
s = set([input().rstrip() for _ in range(n)])
cnt = 0

for _ in range(m):
    t = input().rstrip()
    if t in s:
        cnt += 1

print(cnt)