[백준][이분탐색] 14426.접두사 찾기

14426.접두사 찾기

 

• 풀이
  
  • S를 사전순으로 정렬
    • 접두사 탐색을 위해 정렬 필수
  • 각 검사 문자열 c에 대해 이진 탐색으로 c가 들어갈 위치 찾기 (bisect_left)
    • idx = bisect_left(S, c)
  • 찾은 위치의 문자열가 c를 접두사로 가지는지 확인
    • S[idx][:len(c)] == c → 접두사 여부 판별
    • startswith로도 확인 가능
      • slst[idx].startswith(c)
  • 접두사면 카운트 증가

from bisect import bisect_left

n, m = map(int, input().split())
slst = sorted(input() for _ in range(n))

clst = [input() for _ in range(m)]

cnt = 0
for c in clst:
    idx = bisect_left(slst, c)

    if idx >= n:
        continue
    if slst[idx][:len(c)] == c:
        cnt += 1

print(cnt)