접두사

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	2191	1055	877	50.460%

문제

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다.

예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다.

하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

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

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에는 단어가 주어진다.

단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

집합에는 같은 단어가 두 번 이상 있을 수 있다.

출력

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

예제 입력 1

6
hello
hi
h
run
rerun
running

예제 출력 1

4

예제 입력 2

6
a
b
cba
cbc
cbb
ccc

예제 출력 2

6

예제 입력 3

6
a
ab
abc
abcd
abcde
abcdef

예제 출력 3

1

예제 입력 4

3
topcoder
topcoder
topcoding

예제 출력 4

2

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 트리
• 트라이

---

통과된 코드

#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

// TrieNode클래스를 사용하여 Trie의 각 노드를 표현
class TrieNode {

public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
    }

};

// Trie 클래스
class Trie {

    // Trie의 루트 노드에 대한 포인터인 Trie개인 멤버 변수
private:
    TrieNode* root; // 루트 노드

// 생성자새 인스턴스를 만들고 Trie를 초기화합
public:
    Trie() {
        root = new TrieNode();
    }

    // 문자열을 받아 Trie에 추가합니다. 
    // 루트 노드에서 시작하여 Trie 아래로 이동하여 단어의 각 문자에 필요한 새 노드를 만듭니다.
    void insert(string word) {
        TrieNode* curr = root; // 시작
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) 
                curr->children[c] = new TrieNode(); // Trie에 없다면 새 노드 생성
            
            curr = curr->children[c]; // Trie에 이미 존재하는 경우 기존 노드로 이동
        }
        // 단어의 끝을 나타내는 isEndOfWord bool값
        curr->isEndOfWord = true;
    }

    // prefix(접두사)로 시작하는 단어가 Trie에 있는지 확인
    int startsWith(string prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) 
                return curr->children.size();
            
            curr = curr->children[c];
        }
        return curr->children.size();
    }
};

int main() {

    Trie trie;
    int N;
    set<string> myV;
    string str;

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> str;
        myV.insert(str); // set으로 중복 제거
        trie.insert(str);
    }

    int res = myV.size();

    for (auto &it : myV) 
        if (trie.startsWith(it) >= 1 ) res--;
    
    cout << res;

    return 0;
}