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

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

 

제출코드

import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())
N_set = set()
M_list = []
res = 0
for _ in range(N):
    N_set.add(input())
for _ in range(M):
    M_list.append(input())
for i in M_list:
    if i in N_set:
        res += 1
print(res)

 

접근방법 및 풀이

이번문제는 M_list에 있는 문자들에서 집합 N_set에 포함되는지 안되는지 확인하는 문제였다. 

1. N개의 문자열로 이루어진 리스트
2. M개의 문자여로 이루어진 리스트

두개를 입력받고 그냥 for문 돌려서 M_list에 있는 문자열들이 N_set에 존재하는지 in만 해주면 되는 문제였다.

set의 in함수는 O(1)의 시간복잡도를 가졌기 때문에 O(N+M)의 시간복잡도로 풀리는 문제였다.