trie_set of strings_14425

백준의 14425번 문제 문자열 집합을 트라이(Trie)로 풀이해보도록 하겠습니다.

Trie 기법은 보통 Prefix Tree, digital search tree, retrieval tree라고 부른다고 합니다. Trie라는 어원도 retrieval에서 따온거래요!

이 문제를 풀기 전에 백준은 아니지만, 프로그래머스의 문제를 먼저 풀어보시길 권유드립니다.
실제 제 코드도 아래에 보시면 프로그래머스 문제 풀이 이후에 조금 변형해서 푼것이 티날거에요.ㅎㅎ

문제 URL : https://www.acmicpc.net/problem/14425

프로그래머스 42557 풀이 보러가기

Source Code :

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class TRIE {
public:
	// 알파벳이 26개니까
	TRIE * node[26];
	// 문자열의 끝을 표시
	bool finish;

	TRIE() {
		for (int i = 0; i < 26; i++) {
			node[i] = NULL;
		}
		finish = false;
	}
	~TRIE() {
		for (int i = 0; i<10; i++) {
			if (node[i]) {
				delete(node[i]);
			}
		}
	}

	void insert(const string &s, int idx) {
		if (s.size() <= idx) {
			finish = true;
		}
		else {
			int tmp = s.at(idx) - 97;	// ascii
			if (node[tmp] == NULL) {
				node[tmp] = new TRIE();
			}
			node[tmp]->insert(s, idx + 1);
		}
	}

	bool find(const string &s, int idx) {
		if (s.size() <= idx) {
			if (finish == true) {
				return false;
			}
			else {
				return true;
			}
		}

		int tmp = s.at(idx) - 97;
		//if (node[])
		if (node[tmp] != NULL) {
			return node[tmp]->find(s, idx + 1);
			//return false;//같다고 바로 끝내버리면안돼고 끝까지 같은지 봐야하거든..
		}
		else {
			return true;
		}
	}
};

TRIE t = TRIE();
int solution(vector <string> phone_book, int n) {
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		t.insert(phone_book[i], 0);
	}

	for (int i = n; i < phone_book.size(); i++) {
		if (t.find(phone_book[i], 0) == false) {
			cnt++;
		}
	}

	return cnt;
}

int main(void) {
	vector <string> dictionary;
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n+m; i++) {
		string tmpStr;
		cin >> tmpStr;
		dictionary.push_back(tmpStr);
	}
	
	cout << solution(dictionary, n);

//	int n;
//	cin >> n;
	return 0;
}

개인이 공부하고 포스팅하는 블로그입니다. 작성한 글 중 오류나 틀린 부분이 있을 경우 과감한 지적 환영합니다!