백준 19585 - 전설 (C++)

문제

• 문제 링크

  
   BOJ 19585 - 전설 
  

• 문제 요약

$C$가지의 색상과 $N$개의 닉네임이 주어진다.
색상과 닉네임을 순서대로 이어붙여 팀명을 지으면 ICPC 리저널에서 수상할 수 있을 때, $Q$개의 쿼리에 대해 해당 팀이 수상할 수 있는지 여부를 판단해보자.

• 제한

TL : $3$ sec, ML : $1024$ MB




$1 ≤ C, N ≤ 4,000$

$1 ≤ Q ≤ 20,000$

모든 색상 이름의 길이와 닉네임의 길이는 1,000글자를 넘지 않는다.

각 문자열은 중복되지 않으며 알파벳 소문자로만 이루어져 있다.

알고리즘 분류

• 자료 구조(data structures)
• 문자열 (string)
• 트리 (trees)
• 트라이 (trie)
• 해시를 사용한 집합과 맵 (hash _ set / map)

풀이

  당연히 무식하게 다 돌아볼 순 없고, 좀 더 효율적인 무식함을 발휘하자.

각 팀명에 대해 접두사(색상)를 trie로 관리해 필요한 만큼만 분기하며, 그 뒤 나머지 문자열(닉네임)을 hash_set으로 관리해보자.

이를 수행하기 위해선 $C$개의 색상을 모두 트라이에 올려주는 작업 ( $O(C * 1000)$ ) 과 hash_set에 $N$개의 닉네임을 모두 올려주는 작업 ( 약 $O(N)$ ) 을 전처리 해 주어야 한다.
트라이에 색상 문자열들을 올리면서 문자열이 끝나는 부분마다 마킹해두자.

쿼리마다 위에서 전처리한 정보를 바탕으로 탐색해 보면 된다.

이때 중요한 것은 무분별하게 계속 색상 / 닉네임 으로 쪼개보는 것이 아닌 마킹해 둔 지점에서만 쪼개 보는 것이다.
만약 임의의 시점에서 마킹이 돼있음과 동시에 나머지 sub string이 hash_set에 있다면 조건을 충족하는 문자열이므로 "Yes", 이러한 순간이 한 번도 오지 않는다면 "No"를 출력해 주면 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
unordered_set <string> S;
string s;
struct T
{
    map <char, T*> p;
    bool x{};
    void push(int i)
    {
        if (i == s.size()) x = 1;
        else
        {
            char t(s[i]);
            if (!p.count(t)) p[t] = new T();
            p[t]->push(i + 1);
        }
    }
    int f(int i)
    {
        if (!p.count(s[i]) || i == s.size()) return 0;
        if (p[s[i]]->x && S.count(s.substr(i + 1))) return 1;
        return p[s[i]]->f(i + 1);
    }
};
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    T R{};
    while (n--) cin >> s, R.push(0);
    while (m--) cin >> s, S.insert(s);
    for (cin >> n; n--;) cin >> s, cout << (R.f(0) ? "Yes" : "No") << '\n';
}

comment

끝