(Python) 백준 14425

백준 14425

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초 (https://www.acmicpc.net/problem/14425#)	1536 MB	29788	16068	12066	53.717%

문제

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

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

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

---

답안

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
strings = set()
result = 0

for _ in range(n):
    strings.add(input())

for _ in range(m):
    if input() in strings:
        result += 1

print(result)

풀이

코드는 아주 쉽다. strings라는 이름의 set을 만든 뒤, 입력된 값이 그 set에 존재하는지 확인해 그 수를 세는 것이다.

하지만 이 문제에서 중요한 것은, 사용하는 자료구조의 종류이다.

만약 strings를 담는 자료구조를 리스트로 하면, 백준에서 돌렸을 때 시간 초과 오류가 난다.

strings에서 어떤 element가 있는지 검색하는 과정에서 시간이 오래 걸리기 때문이다.

파이썬에서 list는 linked list로 구현되어 있고, set은 해쉬 테이블로 구현이 되어 있는데,

list는 검색을 할 때 $O(n)$의 시간복잡도를 가지는 반면, set은 $O(1)$의 시간복잡도를 가지기 때문에,

검색에 시간이 오래 걸릴 것이라고 판단된다면 set을 사용하는 것이 좋다.