(14425) 문자열 집합

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 4번째

 

 

 

집합과 맵 단계에서 푼 적 있는 문자열 집합 문제지만, 트라이 자료구조 연습을 위해 트라이로 풀어보라고 준 문제.

옛날 계정에서 쓴 트라이 구조를 보니 char*를 쓰고 map 구조로 만들고 탐색에 []를 사용하는 등 코드에 몇몇 문제점이 보여 트라이 구조체를 새로 만들었다.

C++17에서 지원하는 string_view를 이용하면 연산 속도도 빠르고 자료형 통일도 필요없고 가독성도 좋다.

 

트라이를 구현할 때 다음 글자를 나타내는 자료 구조로 map<char,Trie*>이나 Trie* 배열 두 가지를 가장 많이 사용하는데,

map은 탐색하며 내려가는 시간이 로그 시간인 반면 배열은 상수 시간이기 때문에 속도는 배열이 훨씬 빠르다.

하지만 배열 방식은 노드를 새로 만들 때마다 항상 가능한 글자수 크기의 포인터 배열을 선언해야 하기 때문에 메모리 사용량이 많고 특히 PS에서는 문자끼리 굉장히 희소하게 떨어진 저격 데이터가 들어오면 메모리 초과가 날 위험도 있다(실무에서도 메모리 문제 때문에 잘 안 쓴다고 한다).

쉽게 말해 시간이 빡빡하면 배열 방식을, 메모리가 빡빡하면 map 방식을 쓰면 된다.

 

하지만 비효율적이던 옛날 코드가 아닌 string_view 등으로 최적화한 지금 코드라면 괜찮지 않을까? 해봐야 할 것 같다.

 

추가) 아스키 거리 문제를 풀면서 새로 알게 된 정보인데, 세그먼트 트리를 배열로 구현하는 것처럼 전체 트라이를 배열 또는 벡터로 만들고 다음 노드의 정보를 포인터 대신 int형의 배열 인덱스로 저장하는 배열형 트라이를 쓰면 메모리를 훨씬 절약할 수 있다고 한다.

 

 

 

#include <iostream>
#include <map>
using namespace std;

struct Trie {
  bool finish= false;
  map<char, Trie*> next;
  ~Trie() { for(auto& iter:next)  delete iter.second; }
  
  void insert(string_view s){
    if(s.empty()) { finish= true;  return; }
    
    if(next[s[0]]==nullptr)  next[s[0]]= new Trie();
    next[s[0]]->insert(s.substr(1));
  }
  
  bool find(string_view s){
    if(s.empty())  return finish;
    
    auto iter= next.find(s[0]);
    if(iter==next.end())  return false;
    return iter->second->find(s.substr(1));
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, ans= 0;
  Trie* root= new Trie();
  
  cin >> n >> m;
  
  while(n--){
    string s;
    
    cin >> s;
    
    root->insert(s);
  }
  
  while(m--){
    string s;
    
    cin >> s;
    
    ans+= root->find(s);
  }
  
  cout << ans;
  
  return 0;
}

struct Trie {
  bool finish= false;
  Trie* next[26]= {nullptr, };
  ~Trie() { for(int i=0;i<26;i++)  if(next[i]!=nullptr)  delete next[i]; }
  
  void insert(string_view s){
    if(s.empty()) { finish= true;  return; }
    
    int idx= s[0]-'a';
    if(next[idx]==nullptr)  next[idx]= new Trie();
    next[idx]->insert(s.substr(1));
  }
  
  bool find(string_view s){
    if(s.empty())  return finish;
    
    int idx= s[0]-'a';
    if(next[idx]==nullptr)  return false;
    return next[idx]->find(s.substr(1));
  }
};