[python] 백준 14426 접두사 찾기

https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

 

 

문제 해결

• 하나씩 비교를 하면 시간복잡도가 매우 크다.
• 따라서 정렬을 한 후에 사전식 배열 비교를 한다.
• S에 포함되어있는 문자열과 검사해야하는 문자열을 비교해서 포함하면 정답+1과 다음 검사해야하는 문자열을 비교를 한다.
• 만약 포함여부에 해당하지 않고 S에 포함되어있는 문자열의 사전식 배열이 더 뒤이면 검사해야하는 문자열을 다음 것으로 넘긴다.
• 만약 포함여부에 해당하지 않고 S에 포함되어있는 문자열의 사전식 배열이 더 앞이면 S에 포함되어 있는 문자열을 다음 것으로 넘긴다.

 

CODE

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, m = map(int, input().split())
    S = []
    for _ in range(n):
        S.append(input().strip())
    S.sort()
    answer = 0
    s = []
    for i in range(m):
        test = input().strip()
        s.append(test)
    s.sort()
    i = 0
    j = 0
    while i<n and j<m:
        if S[i][:len(s[j])] == s[j]:
            answer += 1
            j += 1
            continue
        elif S[i] > s[j]:
            j += 1
            continue
        elif S[i] < s[j]:
            i += 1
            continue
    print(answer)