[BOJ] 1141 - 접두사

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

BOJ - 접두사

문제 유형: 트라이, 정렬, 그리디

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 128MB

 

문제

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

 

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

문자열들을 길이우선으로 내림차순 정렬해주고, 트라이를 만들어서 트라이에 노드가 새로 추가되게 되면 접두사X집합에 단어를 하나 넣는것과 같다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;

bool isPrefix(const string &p, const string &word) {
  int len = p.size();
  for (int i = 0; i < len; ++i) {
    if (p[i] != word[i])
      return false;
  }
  return true;
}

class TrieNode {
public:
  char key;
  TrieNode *children[26];

  TrieNode(char k) {
    this->key = k;
    for (int i = 0; i < 26; ++i) {
      children[i] = nullptr;
    }
  }
};

class Trie {
public:
  TrieNode *root;

  Trie() { root = new TrieNode('-'); }

  bool insert(const string &word) {
    auto curr = root;
    int i = 0;
    int m = word.size();

    bool flag = false;

    while (i < m) {
      int charNum = word[i] - 'a';
      if (curr->children[charNum] == nullptr) {
        flag = true;
        curr->children[charNum] = new TrieNode(word[i]);
        curr = curr->children[charNum];
      } else {
        curr = curr->children[charNum];
      }
      ++i;
    }

    return flag ? 1 : 0;
  }
};

int main(int argc, char *argv[]) {
  cin >> n;
  vector<string> words(n);
  for (int i = 0; i < n; ++i) {
    cin >> words[i];
  }

  sort(words.begin(), words.end(),
       [](const auto &a, const auto &b) { return a.size() > b.size(); });

  int ans = 0;
  Trie *t = new Trie();
  for (const auto &word : words) {
    ans += t->insert(word);
  }

  cout << ans << "\n";

  return 0;
}