[백준] 14425 문자열 집합

📖 문제

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

💻 내 코드

import sys
n, m=map(int, sys.stdin.readline().split())

mlist=dict()


for i in range(n):
    s=sys.stdin.readline().strip()
    mlist[s]=True
    
cnt=0
for _ in range(m):
    word=sys.stdin.readline().strip()
    if word in mlist.keys():
        cnt+=1
print(cnt)

💡 풀이

처음에 제출한 코드

import sys
n, m=map(int, sys.stdin.readline().split())

mlist=[]


for i in range(n):
    mlist.append(sys.stdin.readline().strip())
cnt=0
for i in range(m):
    word=sys.stdin.readline().strip()
    for j in range(n):
        if word==mlist[j]:
            cnt+=1
            continue
print(cnt)

• 결과는 제대로 나오는 것 같은데 시간 초과가 떠서 다른 풀이 방법이 생각이 안나서 검색해봄
• list형은 시간 복잡도가 O(N)이고 set과 dictionary는 O(1)임을 알게 됨
• dictonary를 이용하여 key에 저장하고 찾을 때 mlist.keys()에 포함되는지 확인하는 방법으로 해결