[백준 19585번] 파이썬 - 전설

백준 19585 - 전설

시간 제한 3초, 메모리 제한 1024MB

# 조건

• Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다.
• 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수상할 수 있을지 전설에 기반해 알려주는 프로그램을 작성하자.

입력

• 첫째 줄에는 색상의 종류 C와 닉네임의 개수 N이 주어진다. (1 ≤ C, N ≤ 4,000)
• 다음 C개의 줄에는 색상 이름 C개가 한 줄에 하나씩 주어진다.
  • 색상 이름은 중복되지 않는다.
• 다음 N개의 줄에는 Sogang ICPC Team 구성원들의 닉네임 N개가 한 줄에 하나씩 주어진다.
  • 닉네임도 중복되지 않는다.
• 다음 줄에는 팀의 개수 Q가 주어진다. (1 ≤ Q ≤ 20,000)
• 다음 Q개의 줄에는 팀명 Q개가 한 줄에 하나씩 주어진다.
  • 팀명은 중복되지 않는다.
• 모든 색상 이름의 길이와 닉네임의 길이는 1,000글자를 넘지 않는다.
• 모든 팀명은 2,000글자를 넘지 않는다.
  • 모든 문자열은 알파벳 소문자로만 이루어져 있다.

출력

• 팀명이 입력된 순서대로, 전설에 따라 해당 팀이 다음 리저널에서 수상할 수 있다면 Yes, 아니라면 No를 출력한다.

# 접근 방법

• 완점 탐색으로 모든 조합을 만들면 당연히 시간 초과가 발생한다.
• 따라서, 문자열 탐색에 용이한 트라이 자료구조를 활용해준다.
• 입력받은 색깔의 단어를 순회하며 딕셔너리를 활용한 트라이 구조로 만들어준다.
  • red를 입력받은 경우 colors 딕셔너리에 r이 있는지 체크 후 없다면
  • r: {} 생성 해준 후 현재 위치를 colors[r]로 변경 후 e를 체크, 마찬가지로 위치 변경 후 d를 체크해준다.
• 또한, 닉네임의 경우는 set 자료구조에 저장해주는데
  • set의 경우 해쉬 테이블로 구현되어 있기 때문에 O(N)의 시간 복잡도를 같은 리스트보다 참조가 O(1)로 빠르기 때문이다.
• 팀 명을 입력받으며 앞에서부터 colors 딕셔너리를 순회해주면서 색깔이 있는지 체크해주고
  • 존재한다면, 색깔 길이를 닉네임 시작 인덱스로 사용하여 set에 존재하는지 체크해준다.

import sys  
input = sys.stdin.readline  

def check(word):  
    depth = colors  
    for idx, w in enumerate(word):  
        if depth.get('finish') and word[idx:] in nickname:  
            return 1  
        if not depth.get(w):  
            return 0  
        depth = depth[w]  


N, M = map(int, input().split())  
colors = dict()  

# color는 트라이 구조로 저장해주기  
# 마지막 단어 뒤에 finish 추가  
# 추가하지 않는 경우 팀 명 앞에 색깔을 확인 할 때 잘못된 답 뱉을 수 있음  
# red 색깔이 있고 drain이란 닉네임이 있을 때 redrain 이라는 팀명이 True가 되게 됨  
for _ in range(N):  
    depth = colors  
    for w in input().rstrip():  
        if not w in depth:  
            depth[w] = {}  
        depth = depth[w]  
    depth['finish'] = 1  

# 리스트의 참조 시복 -> O(n)  
# set의 참조 시복 -> O(1) 이므로 set에 저장 해주기  
nickname = set()  
for _ in range(M):  
    nickname.add(input().rstrip())  

for _ in range(int(input())):  
    team_name = input().rstrip()  
    if check(team_name):  
        print('Yes')  
    else:  
        print('No')