개미굴
이 문제는 Trie를 사용해서 해결해야 하는 문제였습니다. 정작 이 문제를 해결할 때는 이 알고리즘을 사용해서 해결해야 한다는 생각 없이 단순히 트리를 만들어내야 한다는 생각으로 해결하였습니다.
class Trie {
constructor() {
this.children = new Map();
this.isEndOfWord = true;
}
insert(word) {
let current = this.root;
for (const ch of word) {
const index = ch.charCodeAt(0) - "a".charCodeAt(0);
if (current.children[index] === null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
search(word) {
let current = this.root;
for (const ch of word) {
if (!current.children.has(ch)) {
return false;
}
current = current.children.get(ch);
}
return current.isEndOfWord;
}
}
위와 같이 작성되어 있는 하나의 노드를 기준으로 계속해서 children 을 추가해가면서 단어를 추가하거나 트리의 관계를 그려내는 알고리즘입니다. 예를 들어, desktop 이라는 단어를 Trie 를 사용하여 트리를 만들어 본다고 가정해보겠습니다. 이 경우
const str = ["d", "e", "s", "k", "t", "o", "p"];
위와 같이 단어를 나눈 후 각 단어를 앞서 만들었던 Trie 를 통해서 관계를 표현합니다.
const root = new Trie();
const str = ["d", "e", "s", "k", "t", "o", "p"];
root.insert(str);
위와 같이 관계를 포함하게 될 경우 d -> e -> s -> k -> t -> o -> p 와 같이 트리 구조가 구성이 됩니다. 이 후 만약 design 이라는 단어를 insert 할 경우 d -> e -> s 가 관계성을 갖고 s 이후에 i -> g -> n 의 새로운 관계를 갖게 되어서 각 단어의 관계, 트리의 관계에 대해서 표현하고 탐색할 수 있게 됩니다.
철로
최대 개수를 구할 경우에는 최대 개수를 하나하나 세는 것이 아닌 "최대 집합의 크기" 를 구하는 것이 문제를 해결하는 방법이라는 것을 잊지 말아야 합니다.
특정 조건을 하나하나 세는 것은 최대일 경우를 세는 과정에서 조건에 부합하지 않는 경우 기존의 집합을 모두 깨버리고 새롭게 세는 과정을 갖기 때문에 언제나 최대 값을 보장할 수 없다는 것을 주의해야 합니다. 최대, 최소는 "집합의 크기" 가 최대인 경우, 최소인 경우를 구해야 한다는 것입니다.