📢 14425번 문제

백준 문제 링크

🔎 풀이

사용언어 : python

list를 사용했을 때 시간초과는 안나오지만, 다른 자료형에 비해 오래걸린다.

💡 자료형에 따른 시간복잡도

list 자료형에서는 삽입, 탐색, 제거,포함여부의 경우 O(N)의 시간복잡도를 가지고 있고,
Set, Dictionary에서는 O(1)의 시간복잡도를 가지고 있다.
즉 순서가 있거나. index요소에 접근할 때에는 list 사용하고
값의 탐색이나 확인은 Dictionary나 set 자료형을 사용해주는 것이 좋다.

딕셔너리 함수
dict[key] = value : Dictionary 추가
key in dict : True False를 반환
dict.get(key) : 해당 키값 리턴, 없으면 None 리턴

집합
set.add(value) : 원소 추가
value in set : 원소 찾기

🔎 코드

✔ 리스트 사용

N, M = map(int, input().split())
S = []
for i in range(N):
    s = input()
    S.append(s)
result = 0
for j in range(M):
    string = input()
    if string in S:
        result += 1
print(result)

✔ Dict 사용

N, M = map(int, input().split())
S = dict()

for i in range(N):
    s = input()
    S[s] = True

result = 0

for j in range(M):
    string = input()
    if S.get(string):
        result += 1
print(result)

✔ Set 사용

N, M = map(int, input().split())
S = set() # 빈 집합 생성

for i in range(N):
    s = input()
    S.add(s) # 원소 추가

result = 0

for j in range(M):
    string = input()
    if string in S: # 값 찾기
        result += 1
print(result)