링크 : https://www.acmicpc.net/problem/14425
14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
- 문제
- 소요시간: 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() 함수를 사용하자
'알고리즘(백준) > 자료구조' 카테고리의 다른 글
| [알고리즘/자료구조] 4358번 : 생태학 - python (0) | 2023.03.17 |
|---|---|
| [알고리즘/자료구조] 11279번 : 최대 힙 - python (0) | 2023.03.15 |
| [알고리즘/자료구조] 1620 번 : 나는야 포켓몬 마스터 이다솜 - python (0) | 2023.03.13 |
| [알고리즘/자료구조] 2800번 : 괄호제거 - python (0) | 2023.03.11 |
| [알고리즘/자료구조] 1874번 : 스택 수열 - python (0) | 2023.03.10 |