プログラマの電話リスト

質問リンク

https://programmers.co.kr/learn/courses/30/lessons/42577

質問する

に答える

詩を解く
1-1の電話帳を並べる
ステップ1～2では、ハッシュに挿入する前に、文字を追加して文字列を作成し、接頭辞が存在するかどうかを確認します.
1～3接頭辞が存在しない場合は、ハッシュ・テーブルに挿入します.
簡単ですが、時間の複雑さの観点から効率が悪いです.

ストライプデータ構造を使用して解く
これは三重データ構造を利用した基本的なタイプの問題である.
以前は似たようなタイプの解題をしていたが,最初からtrie資料構造を用いた解題を思いついた.
(*詳細な解凍コードを表示)

試行錯誤

亥時
説明は簡単で、あまり難しくありません.
三輪車
最初は,以下の値が存在することを確認するために,繰り返し文を用いてチェックしたが,時間的複雑さの面で効率が低下した.
より効率的な方法を考慮しisnext変数を設定し,性能を改善した.

コード#コード#

code 1ハッシュデータ構造

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

bool solution(vector<string> phonebook) {

	sort(phonebook.rbegin(), phonebook.rend());
	unordered_map<string, int> m;
	for (int i = 0; i < phonebook.size(); i++) {
		string temp = "";
		for (int j = 0; j < phonebook[i].size(); j++) {
			temp += phonebook[i][j];
			if (m[temp] != 0) return false;
		}
		m[temp]++;
	}
	return true;

}

code 2三層構造

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;


struct Trie {
	bool finish;
	bool isnext;
	Trie* next[10]; 
	
	Trie() : finish(false),isnext(false) { 
		memset(next, 0, sizeof(next));
	} 

	~Trie() { 
		for (int i = 0; i < 10; i++) 
			if (next[i]) delete next[i]; 
	} 
	
	bool insert(const char* key) { 
		if (finish) {
			return false;
		}

		if (*key == '\0') {
			finish = true;
			if (isnext) return false;
			return true;
		}
		else { 
			int curr = *key - '0'; 
			if (next[curr] == NULL) {
				next[curr] = new Trie();
				isnext = true;
			}
			return next[curr]->insert(key + 1);
		} 

	} 
	
};


bool solution(vector<string> phonebook) {

	Trie* root = new Trie();
	for (int i = 0; i < phonebook.size(); i++) {
		char cstr[21];
		strcpy(cstr, phonebook[i].c_str());
		
		bool check = root->insert(cstr);
		if (!check) {
			return  false;
		}
	}

	return true;
}

ポスト

trie資料の構造を復習する機会です.
https://eun-jeong.tistory.com/29
このリンクでは,三色資料の構造に関する内容を整理した.