9/15 (금) Trie 클래스를 구현해보다 TIL

공부한 것

LeetCode #208. Implement Trie (Prefix Tree)

=> Trie(트라이) 클래스를 구현하였다. 내가 만든 1차원 배열을 이용한 해답과 달리 실제로는 거의 무한히 중첩되는 배열을 사용하여 구현하는 것이었다. private 속성과 메소드를 이용하고 recursive array type이라는 타입 문법을 사용하는 등 안목을 넓힐 수 있었다.

다음은 그렇게 구현하여 무한히 중첩되는 것 같은 배열이 어떻게 작동하는지 이해하는 데 도움이 된 이미지이다.

https://www.youtube.com/watch?v=-urNrIAQnNo

신기하게도 내가 구현한 Trie 클래스는 메모리는 매우 적게 드는데 시간은 엄청 오래 걸리고, 반대로 Trie답게 제대로 만든 클래스는 메모리가 많이 필요하고 걸리는 시간은 1/3정도 줄어들었다.

(느리고 가벼운) 내 클래스 구현:

class Trie {
    words: string[]
	constructor() {
		this.words = [];
    }

	insert(word: string): void {
		this.words.push(word);
	}

	// 정확한 매칭
	search(word: string): boolean {
		return this.words.includes(word);
	}

	// 앞의 일부분만 매칭되면 ok
	startsWith(prefix: string): boolean {

		for (let word of this.words) {
			if (word.startsWith(prefix)) return true;
		}

		return false;
	}
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

(빠르고 무거운) 다른 해답:

// 다른 해답:
const dict = "abcdefghijklmnopqrstuvwxyz";
const charMap = new Map([...dict].map((v, i) => [v, i]));
// => 'charCodeAt()' 대체용 map
	// charMap = { a: 0, b: 1, ..., y: 24, z: 25}

// recursive array type(?)
type TrieNode = TrieNode[];

class Trie {
	#root: TrieNode[] = Array(dict.length); // 26개 길이의 빈 배열
	#ends = new WeakSet<TrieNode>();

	insert(word: string): void {
		let node: TrieNode[] = this.#root; 

		// "coffee"를 인수로 받았다면 'c','o'...의 각 문자에 대하여
		// charMap.get('c') = 2
		// o = 14
		// f = 5
		// f = 5
		// e = 4
		// e = 4
		for (const char of word) {
			// 해당하는 영문자 번호에 해당하는 위치로 찾아간다. 
			// 다음 노드로 이동하고 필요하다면 새로 만든다. 
			node = node[charMap.get(char)!] ??= Array(dict.length);
		}

		this.#ends.add(node);
	}

	// 노드를 순회하며 주어진 word의 마지막 노드 혹은 null을 반환한다.
	#search(word: string): TrieNode | null {
		let node = this.#root;
		
		for (const char of word) {
			const next = node[charMap.get(char) ?? -1];
			// char가 영문 소문자가 아니거나 해당 알파벳이 이전에 단계별로 등장한 적이 없는 문자라면...
			if (!next) return null;
			node = next;
		}

		return node;
	}

	search(word: string): boolean {
		return this.#ends.has(this.#search(word) ?? []);
	}

	startsWith(prefix: string): boolean {
		return this.#search(prefix) !== null;
	}
}

Uploaded by N2T

공부한 것

티스토리툴바