백준 14425 문자열 집합 - python

첫 번째 코드(시간 초과)

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = []
for i in range(N):
    S.append(input())
ans = 0
for _ in range(M):
    t = input()
    if t in S:
        ans += 1
print(ans)

두 번째 코드(성공)

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = set()
for i in range(N):
    S.add(input())
ans = 0
for _ in range(M):
    t = input()
    if t in S:
        ans+=1
print(ans)

list를 쓴 코드는 시간 초과가 나왔고, set을 쓴 코드는 성공했습니다.

t가 S에 있는지 확인할 때, in을 사용했는데 자료 구조에 따라 시간 복잡도가 다른 것이었습니다.

set과 dict는 hash table 구조(key에 데이터를 저장하는 구조, key를 통해 데이터를 받아오기 때문에 빠름)를 사용합니다. (set은 key만 있고, dict는 key와 value가 있음)

hash는 hashing function(key에 대한 산술 연산을 통해 데이터의 위치를 찾는 함수)을 이용하기 때문에 O(1)에서 최악의 경우 O(n)의 시간 복잡도를 갖습니다.