[알고리즘/자료구조] 14425 번 : 문자열 집합 - python

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

14425번: 문자열 집합

 

---

• 문제
• 소요시간: 15분 실패

---

• 설계하기(접근방법) 

1. n, m을 입력받는다

2. 집합 s를 입력받고, 단어를 입력받으며 s 내에 있는지 검사한다

있다면 cnt += 1을 해준다

3.print(cnt)

 

(실패 이유) 

m과 n 을 곱하면 연산량이 1억번이 넘어가므로 일반적인 리스트로는 시간이 초과된다.

파이썬의 딕셔너리 기능을 이용하면 키값을 통해 연산을 O(1)로 만들 수 있다.

이는 딕셔너리가 해시테이블과 헤시함수를 기반으로 작동하고 있기 때문에 가능한 일이다

---

• 코드(출력)

import sys

input = sys.stdin.readline

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

for _ in range(n):
    x = input().rstrip()
    s[x] = True

for j in range(m):
    a = input().rstrip()
    if a in s:
        cnt += 1

print(cnt)

---

• 얻어갈 부분

1. 리스트를 통해 연산을 해서 시간이 초과될 것 같다면 딕셔너리를 이용하자.

2. sys.stdin.readline을 사용하는 경우 개행문자에 주의해 rstrip() 함수를 사용하자