solution 1
function solution(phone_book) {
let trie = new Trie();
phone_book.forEach((phone) => {
trie.addWord(phone);
})
for(let phone of phone_book){
if(!trie.startsWith(phone)){
return false;
}
}
return true;
}
class Node {
constructor(){
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor(){
this.root = new Node();
}
addWord(word){
let current = this.root;
for(let char of word){
if(!current.children[char]){
current.children[char] = new Node();
}
current = current.children[char];
}
current.isEndOfWord = true;
}
startsWith(prefix){
let current = this.root;
for(let char of prefix){
current = current.children[char];
}
const haveChildren = Object.keys(current.children).length;
// Trie를 직접 생성했기 때문에 prefix로 들어온 값들의 마지막이 isEndOfWord임을 알고있는 상태
// 따라서, children을 가지고 있는지만 판단하면 된다.
if(haveChildren){
return false;
}
return true;
}
}접두어를 이용하는 문제였기 때문에 Trie를 떠올렸다.
문제 분류는 Hash로 되어있었지만, 개인적으로 Hash는 접두어 문제에 사용하기 까다롭다고 생각하여
Trie로 문제를 해결하고자 했다.
원리는 다음과 같다.
phone_book에 담겨있는 모든 번호를 Trie에 넣어준다.
그렇게 되면, 각 번호에 대해서 마지막 숫자는 isEndOfWord를 true로 가지게 된다.
만약, 어떤 번호의 마지막 노드의 isEndOfWord가 true인데, children을 가지고 있게 된다면
루트 노드부터 해당 노드까지는 접두어로 사용되고 있는 상황이므로 false를 반환한다.
solution 2
function solution(phone_book) {
let trie = new Trie();
phone_book.forEach((phone) => {
trie.addWord(phone);
})
for(let phone of phone_book){
if(!trie.startsWith(phone)){
return false;
}
}
return true;
}
class Node {
constructor(){
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor(){
this.root = new Node();
}
addWord(word){
let current = this.root;
for(let char of word){
if(!current.children[char]){
current.children[char] = new Node();
}
current = current.children[char];
}
current.isEndOfWord = true;
}
startsWith(prefix){
let current = this.root;
for(let char of prefix){
if(current.isEndOfWord && Object.keys(current.children).length){
return false;
}
current = current.children[char];
}
return true;
}
}startsWith()를 약간 수정했다.
for 내부에서 직접 조건 처리를 하게 되는데,
매번 Object.keys()를 하기 때문에 시간 복잡도는 더 증가했다.
코드 자체는 깔끔해보이지만 유의미한 변화를 가져오지는 않는 것 같다.
solution 3
function solution(phone_book) {
let map = new Map();
phone_book.forEach((phone) => {
if(!map.has(phone)){
map.set(phone, phone);
}
})
for(let phone of phone_book){
let count = 0;
let str = "";
for(let char of phone){
str += char;
if(map.has(str)){
count++;
}
if(count > 1){
return false;
}
}
}
return true;
}Trie로 진행했을 때, 생각보다 시간 복잡도가 높게 나와서 Hash로 문제를 접근해보았다.
우선 phone_book에 있는 값들을 Map에 넣어준 뒤, 각 원소를 순회한다.
이 때, 접두어의 경우 자기 자신이 탐색되는 이슈가 있으므로, count를 통해 접두어 탐색을 진행한다.
접두어를 포함하는 번호가 자기 자신만 있는 상태라면 count는 1로 끝나지만,
두 개 이상이 되는 경우에는 count가 1보다 커지는 것을 이용하는 것이다.
시간 초과
function solution(phone_book) {
let trie = new Trie();
phone_book.forEach((phone) => {
trie.addWord(phone);
})
if(!trie.BFS()){
return false;
}
return true;
}
class Node {
constructor(){
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor(){
this.root = new Node();
}
addWord(word){
let current = this.root;
for(let char of word){
if(!current.children[char]){
current.children[char] = new Node();
}
current = current.children[char];
}
current.isEndOfWord = true;
}
BFS(){
let queue = [];
let node = this.root;
queue.push(node);
while(queue.length){
let poped = queue.shift();
let childrenKeys = Object.keys(poped.children);
if(poped.isEndOfWord && childrenKeys.length > 0){
return false;
}
if(childrenKeys.length === 0){
continue;
}
for(let child of childrenKeys){
queue.push(poped.children[child]);
}
}
return true;
}
}같은 조건을 BFS를 사용하는 것으로 탐색해보았다. 그러나 이번에는 시간 초과가 발생했다.
굳이 따지자면 startsWith()는 DFS의 방식인데,
BFS는 모든 경우의 수를 따지면서 트리의 레벨을 증가시키는 반면,
DFS는 특정 입력값(접두어)에 대하여 가능 여부를 확인해나가는 방식이기 때문에
더 빠르게 해결 할 수 있었던 것으로 예상된다.
