백준 19585번 : 전설 (Python) (트라이 없이)

출처 : https://www.acmicpc.net/problem/19585

import sys
input = sys.stdin.readline

c, n = map(int, input().split())
tree_c = dict()
set_n = set()

def insert(tree, word) :
    cur = tree
    for char in word :
        if char not in cur :
            cur[char] = dict()
        cur = cur[char]
    cur["*"] = len(word)
    
def startswith(tree, word) :
    cur = tree
    for char in word :
        if char not in cur :
            return False
        cur = cur[char]
        if "*" in cur :
            idx = cur['*']
            if word[idx:] in set_n :
                return True
    
for _ in range(c) :
    color = input().rstrip()
    cur = tree_c
    insert(tree_c, color)
for _ in range(n) :
    name = input().rstrip()
    set_n.add(name)

q = int(input())
for _ in range(q) :
    team = input().rstrip()
    if startswith(tree_c, team) :
        print("Yes")
    else :
        print("No")

먼저 트라이(Trie)를 활용한 풀이.

색상은 딕셔너리로 구현한 트라이에 넣고, 닉네임은 set에 넣는다.

트라이의 마지막에는 색상 단어의 길이를 저장한다.

팀명을 트라이에 넣어서 접두사로 일치하는 색상이 있으면, 색상의 길이만큼 앞에서 잘라낸 팀명이 닉네임 set 안에 있는지 확인한다.

이때 일치하는 색상이 여럿 있을 수 있으니(ex 색상 : aa, aab / 팀명 : aabxx) 팀명의 끝까지 탐색해야한다.

 

정답 제출 후 다른 사람의 코드를 보니 트라이 필요가 없더라...

색상과 닉네임 각각 set에 넣어주고 팀명의 앞에서부터 앞뒤로 쪼개가며 set에 일치하는 값이 있는지 찾아준다.

다른 언어에서도 가능할지는 모르겠다.

import sys
input = sys.stdin.readline

c, n = map(int, input().split())
set_c = set()
set_n = set()
for _ in range(c) :
    set_c.add(input().rstrip())
for _ in range(n) :
    set_n.add(input().rstrip())
    
q = int(input())
for _ in range(q) :
    team = input().rstrip()
    l = len(team)
    answer = "No"
    for i in range(max(1, l - 1000), min(1001, l)) :
        if team[:i] in set_c and team[i:] in set_n :
            answer = "Yes"
            break
    print(answer)