[Python] BAEKJOON 14425번 문자열집합

문제

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

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

입력

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

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

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

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

출력

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

예제 입력 1 

5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

예제 출력 1 

4

 

 

try1) 

시간초과 코드 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
checkset = []
cnt = 0 
for i in range(N):
    checkset.append(input())
for i in range(M):
    word = input() 
    for j in range(N):
        if checkset[j] == word:
            cnt += 1 
print(cnt)

 

 

sol1) 

간신히 통과하는 코드(try1 변형)

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
checkset = []
cnt = 0 
for i in range(N):
    checkset.append(input())
for i in range(M):
    word = input() 
    if word in checkset:       #try1 부분 이중 for문 대신 if문 바로 사용
        cnt += 1 
print(cnt)

3752ms 너무 오래 걸렸다. 아무래도 for문이 두번 들어갔기 때문일 것.

하지만, 극한의 숏코딩은 존재했고, 두자리 단위까지 시간을 단축한 코드를 보고 자괴감에 빠졌다. 그래서 나도 도전해봤다. 

참고로 input = sys.stdin.readline을 사용해 input()보다 더 빨리 입력받을 수 있는데, sys.stdin.readline역시 대체 가능하다. (반복 입력을 받는 상화에서 input()보다 성능이 좋다.)

open(0).read() == sys.stdin.read() 와 같이.