[BOJ] 14426 - 접두사 찾기 (Python)

 

 

아이디어 #1

 

트라이를 이용하여 접두사인 문자열의 개수를 센다.

 

 

풀이 #1

 

예전에 for문으로 접두사를 찾는 코드를 PyPy3로 제출해서 통과했었는데 재채점 후 시간 초과가 되어 다시 풀어보았다.

 

클래스로 구현한 트라이 trie를 생성하여 insert로 문자열들을 트라이에 넣고, search로 접두사 여부를 판단한다.

 

트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다.

insert 메서드는 문자열의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다.

search 메서드는 문자열의 문자들을 루트 노드에서부터 차례로 찾고, 문자열이 존재하면 1, 그렇지 않으면 0을 반환한다.

 

import sys

input = sys.stdin.readline

class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, S):
        node = self.root
        for c in S:
            if c not in node:
                node[c] = dict()
            node = node[c]

    def search(self, S):
        node = self.root
        for c in S:
            if c in node:
                node = node[c]
            else:
                return 0
        return 1

N, M = map(int, input().split())
trie = Trie()
res = 0
for _ in range(N):
    S = input().rstrip()
    trie.insert(S)
for _ in range(M):
    S = input().rstrip()
    res += trie.search(S)
print(res)

 

 

 

아이디어 #2

 

bisect 모듈을 이용하여 이분 탐색으로 접두사로 포함되는 문자열을 찾는다.

 

 

풀이 #2

 

N개의 문자열들을 오름차순 정렬하여 리스트 S에 저장한다.

bisect_left 함수로 S에서 검사할 문자열이 삽입될 수 있는 인덱스를 찾고,

해당 인덱스에 존재하는 문자열의 접두사로 포함되면 결과값 res를 1 증가시킨다.

 

import sys
from bisect import bisect_left

input = sys.stdin.readline

N, M = map(int, input().split())
S = sorted([input().rstrip() for _ in range(N)])
res = 0
for _ in range(M):
    temp = input().rstrip()
    idx = bisect_left(S, temp)
    if idx < N and S[idx].startswith(temp):
        res += 1
print(res)