백준 5467 - Type Printer (C++)

문제

• 문제 링크

  
   BOJ 5467 - Type Printer 
  

• 문제 요약

출력해야 하는 $N$개의 단어 목록이 주어진다.
프린터로 $3$가지의 작업을 수행할 수 있을 때, 주어진 단어 목록을 모두 출력하는 최소 작업 경로를 추적해보자.

• 제한

TL : $1$ sec, ML : $128$ MB




$1 ≤ N ≤ 25,000$

각 단어는 소문자로만 구성되며 중복이 없고 20자를 넘지 않는다.

알고리즘 분류

• 자료 구조(data structures)
• 문자열(string)
• 트리(trees)
• 트라이(trie)
• 정렬(sorting)

풀이

   결국 가장 긴 단어를 맨 마지막으로 출력해야 한다는 것은 자명하다.
단어들을 순회함에 있어서 트라이에 $N$개의 단어들을 모두 올린 뒤 이어진 max_size순으로 순회하면 될 듯 하다.

트라이에 단어들을 올리는 것 자체야 크게 어려울 사항이 없지만 max_size순으로 순회하는 것은 약간의 생각이 필요하다.
이를 보다 수월하게 구현할 수 있도록 트라이에 추가 변수(임의의 시점에서 뻗어지는 가장 긴 문자열의 길이)를 이용하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct T
{
    map <char, T*> p;
    int x{}, y{};
    void push(string& s, int i)
    {
        if (i == s.size()) x = 1;
        else
        {
            y = max(y, (int)s.size() - i);
            if (!p.count(s[i])) p[s[i]] = new T();
            p[s[i]]->push(s, i + 1);
        }
    }
};
vector <char> an;
 
void sv(T* t)
{
    if (t->x) an.push_back('P');
    vector <pair<int, char>> V;
    for (auto& [a, b] : t->p) V.emplace_back(b->y, a);
    sort(V.begin(), V.end());
    for (auto& [a, b] : V)
    {
        an.push_back(b);
        sv(t->p[b]);
        an.push_back('-');
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    T* R(new T());
    int n; cin >> n;
    for (string s; n--;)
        cin >> s, R->push(s, 0);
    for (sv(R); an.back() == '-'; an.pop_back());
    cout << an.size() << '\n';
    for (auto& c : an) cout << c << '\n';
}

comment

끝