[Python] 백준 #14425- 문자열집합

문제

---

14425번: 문자열 집합

코드

---

My answer

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cnt = 0

S = {input().strip() for _ in range(n)}

for j in range(m):
    if input().strip() in S:cnt+=1
print(cnt)

 

풀이

---

리스트로 구현을 하면 시간초과가 뜨는데 집합으로 구현을 하면 시간초과가 안난다. 문제에서 집합s에는 같은 문자열이 입력되지 않는다고 왜 집합으로 구현을 해야하는지 이해할 수가 없었는데 검색을 해보고알았다. 같은함수라도 자료형에 따라 시간복잡도가 다르다는 것이다. 우선 in함수를 쓸 때 리스트는 원소들을 하나하나 순회하기 때문에 O(n)의 시간이 걸리는데 집합은 해쉬라는 것을 이용하여 접근하기 때문에 최악은 O(N)이지만 일반적으로는 O(1)이라고 한다...이 외에도 리스트.튜플이 in 시간복잡도가 동일하고, 집합과 딕셔너리가 O(1)이라고 한다.

[Python] 파이썬 in 연산 시간복잡도