문자열 집합(백준 14425번)

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

나의 풀이(참고)

import sys
N,M=map(int,sys.stdin.readline().strip().split())
S=set()
for i in range(N):
    I=sys.stdin.readline().strip()
    S.add(I)
count=0
for j in range(M):
    I2=sys.stdin.readline().strip()
    if I2 in S:
        count+=1
print(count)

• 여기서 중요한 부분은 S=list()가 아닌 S=set()인 것이다.
• list에서는 해당 값이 있는지 없는지 비교하며 찾기 때문에 O(n)의 시간이 걸린다.
• 반면 set() 또는 dict()는 hashtable로 구성되어 있기 때문에, 값을 찾고 없애는 것이 O(1)의 시간이 걸린다.
  • set()은 add()를 통해 key값을 추가해야 한다.
  • 값 여러개를 추가할 때는 s1.update([4, 5, 6])의 형태 사용