[백준/19585] 전설 (Python)

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

19585번: 전설

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:21:08

 

---

 

문제 설명

 

 

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를 출력한다.

 

입력 예시

 

4 3
red
blue
purple
orange
shift
joker
noon
5
redshift
bluejoker
purplenoon
orangeshift
whiteblue

 

출력 예시

 

Yes
Yes
Yes
Yes
No

 

 

---

 

풀이

 

플래티넘 등반은 언제나 힘들다... ps 공부가 더 필요한 시점이 언젠가는 오리라 생각했는데, 지금이 딱 그 시점같아보인다.

 

1.

 

첫 번째 시도로 브루트포스를 생각해 볼 수 있겠다. 그렇다면, (색상 + 팀명)의 총 가짓수는 최대 4000^2가 된다. 첫째로, 시간복잡도 자체가 O(NC) = O(N^2)이 되므로 시간 초과다. 둘째로, 만약 이를 통과한다고 해도 이를 쿼리하는 작업에 문제가 생긴다.

 

쿼리는 최대 20000개까지 들어올 수 있다. 일반적인 리스트 자료구조는 탐색에 O(N)의 시간이 소요되므로, 리스트를 쓰면 시간 초과가 일어난다. 또한, 집합의 경우는 탐색에 O(1)의 시간이 소요되나, 위의 가짓수를 저장하려면 비효율적으로 많은 메모리를 소모하게 된다.

 

2.

 

그렇다면 트라이(Trie)를 시도해 볼 때이다.

 

즉 색상과 이름을 따로 트라이 형태로 저장하여, 쿼리 하나를 검사할 때 이 두 가지 트라이를 이용해볼 수 있겠다. 어떤 idx 시점에서 다음과 같은 경우가 가능하다.

 

• idx 순회를 완료했고, 현재 가리키는 트라이가 이름 트라이이며, 그 트라이에 엔드포인트가 존재할때 : 정답이다. 따라서 Yes를 출력한다. idx 순회를 완료했으나 다음 조건을 만족하지 못한다면(색상 트라이거나, 엔드포인트가 존재하지 않는다면) 정답이 될 수 없다.
• idx 순회 도중, 현재 가리키는 트라이가 색상 트라이이며, 현재 시점에서 엔드포인트가 존재할 때 : 이 경우는 분기할 수 있다. 색상 트라이를 계속 순회할 수도 있고, 또는 이름 트라이로 넘어가 진행해 볼 수 있겠다. 색상에 ('red', 'redish')가 존재하고, 이름에 ('ishman')이 존재하는 경우를 생각해 보자. idx=4일때 'i'문자열이 나온다면, 이는 redish + a 혹은 red + ishman 조합 둘 다 가능하다. 즉 둘 모두를 고려하여야 한다.
• 이외의 경우는 기존 트라이 순회와 동일하게 진행한다.

...하지만 이 경우는 시간 초과를 일으켰다.

 

3.

 

2번이 시간 초과를 일으키는 요소들을 생각해 볼 수 있다. 대표적으로 분기를 처리해야 하는 과정 자체이다. 이 분기 처리를 위해서는 재귀 구조 혹은 큐를 사용한 탐색을 진행해야 하는데, 이 탐색 입출력 자체에 소요되는 시간이 크다.

 

마지막으로 생각해 낸 것은, 트라이 구조와 해시 구조의 혼합이다. 즉 색상 순회를 마치고 이름을 탐색할때, 트라이 구조 대신 해쉬 구조(즉 집합)를 사용해 볼 수 있다. 색상 트라이를 순회하다 만약 현재 시점에서 엔드포인트가 존재할 때, 우리는 인덱스 뒷 문자열이 이름 집합에 포함되어있는지를 검사하면 될 일이다(앞서 말했듯, 이 때 시간복잡도는 O(1)이다. 다만 문자열 슬라이싱이 일어나므로 조금 시간은 오래 걸린다)

 

 

풀이 코드

import sys
input = sys.stdin.readline

C, N = map(int, input().split())
endpoint = '!'

color_dict = dict()
name_set = set()

for _ in range(C) :
  color = input().strip()
  cur_dict = color_dict
  for c in color :
    if c not in cur_dict :
      cur_dict[c] = dict()
    cur_dict = cur_dict[c]
  cur_dict[endpoint] = True

for _ in range(N) :
  name = input().strip()
  name_set.add(name)

Q = int(input())
for _ in range(Q) :
  team = input().strip()
  length = len(team)
  cur_dict = color_dict
  enable = False
  for i in range(length) :
    if endpoint in cur_dict and team[i:] in name_set :
      enable = True
      break
    if team[i] not in cur_dict :
      break
    cur_dict = cur_dict[team[i]]

  print('Yes' if enable else 'No')

풀이 완료@