[알고리즘] 백준 14426 파이썬 - 접두사 찾기

 

14426번: 접두사 찾기

문제

문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다.

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

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구하는 프로그램을 작성하시오.

 

문제풀이

import sys
input = sys.stdin.readline
n,m = map(int,input().strip().split())
#01
tmp = [input().strip() for _ in range(n)]
s = [input().strip() for _ in range(m)]

dic = {}
#02
for x in tmp:
    for i in range(1,len(x)+1): dic[x[:i]] = 1
#03
cnt = 0
for i in s:
    try:
        cnt += dic[i]
    except:
        pass
print(cnt)

- #01 : 입력받은 집합을 tmp에 저장한다. 

           집합에서 접두사의 여부를 확인할 값은 s에 저장한다.

- #02 : tmp의 부분 문자열 모두를 하나씩 인덱싱하여 dic에 값 1로 저장한다.

           (아래 사진과 같은 형태)

- #03 : 만약 dic[i] 값이 존재한다면 cnt에 더한다. 

           즉 존재하면 cnt에 1을 더한다.

           만약 dic[i[가 존재하지 않아 KeyError가 발생하면 pass한다.

           최종적으로 구해진 cnt 값을 출력한다.