백준 19585 전설 (파이썬)

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

19585번: 전설

나의 풀이 (시간 초과)

문제자체는 쉬우나 데이터의 양때문에 시간초과가 났다.

문제 접근은 다음과 같이 하였다.

 

주어진 값

색상의 종류C, 닉네임의 개수 N의 범위는 1이상 4000이하이다.

그리고 팀 Q의 수는 1이상 20000이하이다.

모든 팀명은 2000이하이다.

 

팀명을 처음부터 마지막까지 같은 순회하면서 슬라이싱을 한다. 문제에서는 색상의 이름 + 닉네임일 경우를 판별해야 한다.

이때 슬라이싱하는데 드는 시간 복잡도는 최악의 경우 200백만 이다. 

그렇기에 슬라이싱하며 하나씩 값을 확인한다.

import sys
input = lambda:sys.stdin.readline().rstrip()

numberOfColor, numberOfNickname = map(int, input().split(" "))
colors, nicknames = set(), set()

def isWinner(teamName):
    lengthOfTeamName = len(teamName)
    colorIdx = 0

    for idx in range(lengthOfTeamName):
        if teamName[:idx] in colors:
            colorIdx = idx
            break

    for idx in range(colorIdx, lengthOfTeamName):
        if teamName[idx:] in nicknames:
            return True

    return False

for idx in range(numberOfColor):
    colors.add(input())

for idx in range(numberOfNickname):
    nicknames.add(input())

numberOfTeam = int(input())

for idx in range(numberOfTeam):
    if isWinner(input()):
        print("Yes")
        continue
    print("No")

혹시나 해서 pypy3로 해보았으나 전부 시간 초과가 났다.

정답

"트라이"라는 알고리즘으로 해결하는 문제였다.

비록 트라이를 처음 접해보았지만 내가 이해한 바로는 루트 노드에서 리프노드로만 내려가는 트리 같았다.

그리고 이를 구현하는 방법을 이해하는데 시간이 걸렸는데 이를 시각적으로 표현하면 다음과 같다.

마지막 문자를 의미하는 경우 0을 넣는다.

CAR와 CASE를 트라이로 표현하였을 경우

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

numberOfColor, numberOfNickname = map(int, input().split())
colors = {}

def check(teamName):
    now = colors
    for i in range(len(teamName)):
        if now.get(0) and teamName[i:] in nicknames:
            return True
        if not now.get(teamName[i]):
            return False

        now = now[teamName[i]]

# 트라이 생성
for _ in range(numberOfColor):
    now = colors
    for c in input():
        if not now.get(c):
            now[c] = {}
        now = now[c]
    now[0] = 1

nicknames = set([input() for _ in range(numberOfNickname)])

for _ in range(int(input())):
    if check(input()):
        print("Yes")
    else:
        print("No")