문자열을 이진트리로 하여 prefix에 따라 배치하는 트리를 구현해보려고 한다.
문제 사이트에서 적절한 문제를 선택하여 풀이해 본다.

트라이? 말고 다른 개념도 있었던 것 같은데

#include <iostream>

class Node {
public:
	Node *child[26];	// 알파벳 26개
	bool last;

	Node() {
		for (int index = 0; index < 26; index++) {
			child[index] = NULL;
		}
		last = false;
	}
};

int n;

void insert(Node &node, std::string str, int index) {
	if (index == str.length()) {
		node.last = true;
		return;
	}

	int children = str[index] - 'a';

	if (node.child[children] == NULL) {
		node.child[children] = new Node();
	}

	insert(*node.child[children], str, index + 1);
}

bool find(Node& node, std::string str, int index) {
	if (index == str.length()) {
		return node.last;
	}
	if (node.child[str[index] - 'a'] == NULL) {
		return false;
	}
	return find(*node.child[str[index] - 'a'], str, index + 1);
}

void print_all(Node &node, std::string str, int index) {
	if (node.last) {
		std::cout << str << "\n";
	}

	for (int index = 0; index < 26; index++) {
		char ch;
		if (node.child[index] != NULL) {
			ch = index + 'a';

			print_all(*node.child[index], str + ch, index + 1);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n;

	Node root;

	std::string str;
	for (int count = 0; count < n; count++) {
		std::cin >> str;

		insert(root, str, 0);
	}

	std::string findStr;
	std::cin >> findStr;
	if (find(root, findStr, 0)) {
		std::cout << "YES\n";
	}
	else {
		std::cout << "NO\n";
	}

	print_all(root, "", 0);
}

trie를 구현하는 방식이고,
map으로 구현하는 방법도 존재.

백준 Trie 문제집
https://www.acmicpc.net/workbook/view/6785

1. 5062 - Trie

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T, N;
    cin >> T;

    
    while (T--)
    {
        bool YesFlas = false;
        cin >> N;
        vector<string> Number;

        // 전화번호들을 받는다.
        for (int i = 0; i < N; i++)
        {
            string sinput;
            cin >> sinput;
            Number.push_back(sinput);
        }

        sort(Number.begin(), Number.end());

        for (int i = 0; i < Number.size() - 1; i++)
		{
			if (Number[i] == Number[i + 1].substr(0, Number[i].size()))
            {
                cout << "NO\n";
                YesFlas = true;
                break;
            }				
		}

        if(YesFlas)
        {
            continue;
        }

        cout << "YES\n";      
    }

    return 0;
}

이전에는 그냥 단순히 벡터의 sort후에 해당 길이의 접두사가 존재하는지 찾는 방식으로 풀었다.

include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t, n;
    cin >> t;
    
    for (int i = 0; i < t; ++i) {
        cin >> n;
        vector<string> arr(n);
        for (int j = 0; j < n; ++j)
            cin >> arr[j];
        
        sort(arr.begin(), arr.end()); // 정렬
        unordered_set<string> hash_set;
        bool flag = false;
        for (int j = 0; j < n; ++j) {
            string str = ""; // arr[j]의 접두어
            for (int k = 0; k < arr[j].length() - 1; ++k) { // lengh() - 1 = 같은 단어가 없다는 조건
                str += arr[j][k]; // 접두어 만들기
                if (hash_set.find(str) != hash_set.end()) {
                    flag = true;
                    cout << "NO" << '\n';
                    break;
                }
            }
            if (flag) break;
            hash_set.insert(arr[j]); // 현재 단어 추가
        }
        if (!flag) cout << "YES" << '\n';
    }
}

다른 방식으로 풀면 위와 같다.