공부한 것
- LeetCode #211. Design Add and Search Words Data StructureLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
https://leetcode.com/problems/design-add-and-search-words-data-structure/description/
=> 오늘은 조금 다른 형태의 Trie(트라이) 클래스 구현체를 보았다. 이전에 접한 구현을 Trie1, 이번에 본 구현을 Trie2 클래스라고 나누었을 때 두 클래스의 차이는 search메소드를 재귀 호출 가능하냐(할 필요 있냐)로 볼 수 있고, 그 때문에 커다란 차이가 발생하는데 아래 ‘(참고) 재귀호출이 가능한 이유’에 잘 정리해두었다.
일단 두 문제의 차이는 이렇다.
- Trie1: 찾아야 하는 단어에 와일드카드(’
.’)가 들어오지 않을 것이다. 영문 소문자 26자로만 이루어진 단어가 인수로 주어질 것이라고 가정한다.
- Trie2: 찾아야 하는 단어에 와일드카드(’
.’)가 최대 2개 섞여 있을 것이라고 가정한다.
여기서 차이가 발생한다. 와일드카드(
.)를 마주치면 그 다음 문자가 기록된 적 있는 문자인지 확인해야 한다. 즉, 현재 문자의 위치에 올 수 있는 모든 가능성 있는 문자에 대해 그 다음 문자부터 끝 문자까지가 기록된 적 있는지를 확인하는 재귀함수를 호출해야 하는 것이다.따라서 Trie1에서는 그러지 않아도 됐지만, Trie2에서는 메소드 search를 재귀함수로 만들어야 한다. 와일드카드(
.) 바로 다음 문자가 매칭되는지 여부뿐만 아니라 그 다음에 이어질 문자들도 전부 검사해야 하므로 단순히 그 다음 문자가 매칭되는지만 확인하는 것으로는 구현할 수 없다. 여기서 전체적인 자료구조가 바뀐다.Trie1 클래스:
const dict = "abcdefghijklmnopqrstuvwxyz"; const charMap = new Map([...dict].map((v, i) => [v, i])); // => 'charCodeAt()' 대체용 map // charMap = { a: 0, b: 1, ..., y: 24, z: 25} type TrieNode = TrieNode[]; class Trie1 { #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가 영문 소문자가 아니거나 해당 알파벳이 이전에 단계별로 등장한 적이 없는 문자라면: 곧바로 null을 반환한다. 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; } }
Trie2 클래스:
class Trie2 { isWord: boolean; child: {[Key: string]: Trie2}; constructor() { this.child = {}; this.isWord = false; } addWord(word: string): void { let curr: Trie2 = this; for(const c of word) { if(!curr.child[c]) { curr.child[c] = new Trie2(); } curr = curr.child[c]; } curr.isWord = true; } search(word: string, i = 0): boolean { let curr: Trie2 = this; for(;i < word.length; i++) { const c = word[i]; // '.' 문자가 아니라면 현재 문자에 매칭되는 노드로 curr 포인터를 옮긴다. if(c !== '.') { if(!curr.child[c]) { return false; } curr = curr.child[c]; // '.'문자라면 만약 그 다음 문자에 매칭되는 기록이 존재함을 발견하면 곧바로 전체 true를 리턴한다? 가능한 이유는 재귀함수를 호출하기 때문. } else { for(const key in curr.child) { if(curr.child[key].search(word, i + 1)){ return true; }; } return false; } } return curr.isWord; } }
(참고) Trie2에서 search 재귀 호출이 가능한 이유:
- 클래스가 자기 자신을 중첩으로 가지는 구조가 되도록 만들어서.
- search메소드에서 '현재 포인터'를 root부터 시작하도록 하지 않고 '현재 노드(=this)'부터 가리켜서 검색을 시작하게 만들어서.
- 또한 '현재 문자'부터 순회하게 만들 수 있는 인덱스 정보를 인자로 하나 더 주고 재귀호출하게 만들었다. 즉, 현재 문자, 현재 노드부터 검사를 시작할 수 있도록 만들어서.
- 직접적인 영향은 없지만, 자료구조를 객체로 삼아서 '전체 자식 중에 다음 문자에 매칭되는 게 있나 없나'를 살피는 코드가 많이 줄어든 것도 도움이 된다. 배열로 만들었을 땐 전체를 한 번 순회해야 없음을 확신할 수 있었으므로.
다음 레시피만 보고 Trie2를 직접 작성해보자
: WordDictionary라는 이름의 클래스를 구현하기. 메소드는 addWord와 search만 만들도록 한다. search는 문자 대신
.이라는 와일드카드를 포함하고 있는 단어도 검색할 수 있어야 한다.// 클래스 자체가 자료구조가 되게 만든다. 자료구조는 객체이다. = child라는 이름으로 자가 복제 속성을 갖도록 한다. -> 타입을 어떻게 지정하는가도 눈여겨 볼 포인트. 왜 객체를 자료구조로 갖는 게 편하냐면 나중에 '.'을 검색할 때 다음다음 노드로 해당 문자가 '있는가'를 한 방에 검색하는 데 편리하므로. //^ (속성)child: 먼저 빈 객체로 설정. 자가복제 자료구조라는 것은 제일 처음 타입 지정할 때 명시되고, 실제 적용은 addWord 메소드에서 부여되며, 실제 사용은 search 메소드에서 재귀호출 형식으로 활용된다. //^ (속성)isWord: 어떤 노드가 기록된 적 있는 단어의 끝 문자인지 기록 //^ (메소드)addWord: /* * 1. curr 포인터가 현재 노드(자기 자신)를 가리키도록 설정한다. * 2. word의 문자만큼 순회하며 * 3. 자식 노드 중 현재 문자가 없으면 새롭게 자신 클래스를 만들어 그 자리에 저장한다. * 4. 현재 포인터를 새롭게 만든(아니면 원래 존재했던) 현재 문자에 해당하는 자식 노드로 옮긴다. * 5. 현재 포인터에게 isWord 속성을 true로 저장시켜준다. */ //^ (메소드)search: /* * 1. curr 포인터가 현재 노드(자기자신)를 가리키도록 설정한다. * 2. word의 문자만큼 순회하며 * 3. 현재 문자가 .가 아니면 -> 현재 '가능성(child)'노드 중 c인 애가 있나 검사해서 없으면 바로 false를 반환하고 있으면 그 노드를 curr 포인터가 가리키도록 만든다. (있으면/없으면 의 순서가 바뀌어도 상관없겠다) * 4. 현재 문자가 .면 * 5. 현재 '가능성' 노드를 모두 순회하며 노드 하나하나마다 * 6. word의 현재 문자~마지막 문자까지 검색하는 자기 자신(search)메소드를 재귀호출한다. * 7. 그래서 결과가 참이면(=현재 문자가 .이 아니고 노드로 존재하면 그 노드로 현재 포인터를 옮기고, 노드로 존재하지 않으면 곧바로 false를 반환하며, 현재 문자가 .이면 다시 재귀호출을 반복하는 = 현재 문자가 기록 노드에 존재하지 않으면 곧바로 false를 반환하는) 현재 if도 true로 반환시키고, * 8. '가능성' 노드를 모두 순회할 때까지 true가 나오지 않는다면 모든 가능한 문자에 대해 그 다음 문자가 맞는 게 없었다는 의미로 false를 반환한다. * 9. 마지막으로 현재 노드(포인터)의 isWord를 반환시키면 된다? 왜냐면 2번의 큰 for문을 빠져나온 상황은 word의 끝까지 확인했다는 의민데 지금 시점에서 '단어로서 완결된 저장기록'을 나타내는 isWord가 거짓일 수도 있으니까. 즉, 'note'를 찾고 있는데 저장된 건 'notebook'이었을 때, note까지는 전부 매칭된다고 나올 것이므로 단순히 'note'끝까지 false가 반환되지 않고 무사히 순회가 끝나서 나왔다고 'note'가 있었다는 의미의 true를 반환할 수는 없는 것이다. 9-1. 보충: 다른 클래스에서는 같은 역할을 #end라는 Set에 각 단어의 마지막 노드를 추가시키는 형태로 '끝맺은 단어'인지 아닌지를 나타냈었다. */두 클래스 모두 O(N)의 공간복잡도를 가진다.
구체적으로는 Trie1은 O(26 * C * N)이고, Trie2는 O(2 * C * N)이다. (C는 단어 평균 문자수이고 N은 단어 수임) 둘 다 O(N)인 것은 같지만 그래도 Trie2 방식이 시간도 절약되고(배열 대신 객체 사용) 공간도 더 적게 사용하는 효율적인 구현임을 알 수 있다.
- Trie1: 찾아야 하는 단어에 와일드카드(’
Uploaded by N2T