[알고리즘][C++] 트라이 (Trie)

백준 14425: 문자열 집합

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

14425번: 문자열 집합

 

접근 방향 및 디버깅

 

트라이 구현

- find 를 활용하면 훨씬 시간도 빠르고 구현도 간단한 문제이나, 트라이 자료구조를 학습하는 차원에서 트라이로 구현

- 개별 노드를 담당할 struct 를 구성하고, 단어가 입력될 때마다 각 글자를 트리 형태로 형성

- 단어가 집합에 존재하는지 찾을 때는 구성된 트리를 탐색

- 중요한 점은, 트리를 구성할 때 단어가 끝나는 지점을 명확하게 표시해주어야 검색이 정확하게 된다는 점! 

 

코드

/* 1091816KB 1680ms */
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>

using namespace std;

struct trie {
	int val;
	trie * children[26];

	trie() {
		memset(children, NULL, sizeof(children));
		//for (int i = 0; i < 26; i++) {
		//	children[i] = NULL;
		//}
	}
};

int main() {

	freopen("input.txt", "r", stdin);

	int N, M;
	cin >> N >> M;
	
	trie t = * new trie;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		
		trie * tmp = &t;
		for (int j = 0; j < str.size(); j++) {

			int letter = (int)str[j] - 97;
			if (tmp->children[letter] == NULL) {
				tmp->children[letter] = new trie;
			}
			tmp = tmp->children[letter];
		}
		tmp->val = 1;
	}

	int cnt = 0;
	for (int i = 0; i < M; i++) {
		string str;
		cin >> str;

		bool flag = true;
		trie * tmp = &t;
		for (int j = 0; j < str.size(); j++) {

			int letter = (int)str[j] - 97;
			if (tmp->children[letter] == NULL) {
				flag = false;
				break;
			}
			tmp = tmp->children[letter];
		}

		if (flag && tmp->val) {
			cnt++;
		}
	} 

	cout << cnt;
	return 0;
}

 

 

배운 점

- a ~ z 를 0 ~ 26 의 수로 변환하는 방법으로는 %97 연산 외에도 (int)str - 97 또는 (int)str - 'a' 도 가능하다