[JS] 자동완성 (2018 카카오 3차)

트리구조를 활용하여 만들었다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/17685

프로그래머스

 

확실히 카카오 문제라 그런지 생각할 거리가 조금 있었다.

 

일종의 트리형식으로 자료구조를 만들어서 해결하였다.

 

go, gone, guild 이 있다고 생각할때

 

rootNode를 만들어서 그 다음으로 갈 수 있는 갈래를 만들었다.

 

 

 

g -> o -> n -> e

   ㄴ> u -> i -> l -> d

 

이런식으로 퍼져나가게 만들었다.

 

무조건 첫 단어는 검색해야 하므로 1부터 시작해서 next배열이 1이 아닌경우 해당 글자까지는 작성을 해야한다고 판단하였다.

이때 조금 생각해야 하는 부분은 go와 gone처럼 서로 포함관계가 있는 경우다. 

 

이경우 next배열의 길이로는 생각할 수 없기에 단어가 끝나는 부분의 노드에는 end로 표시를 해두어서 해결해주었다.

 

 

 

 

 

 

class Node {
    constructor(val){
        this.val = val
        this.next = []
        this.end = false
    }
}

function solution(words) {
    const rootNode = new Node(0)
    
    //트리구조로 단어 생성
    for(const word of words){
        let curNode = rootNode
        for (let i = 0 ; i < word.length; i++){
            if(!(curNode.next.find(v=>v.val===word[i]))) curNode.next.push(new Node(word[i])) 
            curNode = curNode.next.filter(v => v.val===word[i])[0]
        }
        curNode.end = true
    }
    let ret = 0;
    
    for(const word of words){
        let curNode = rootNode.next.filter(v => v.val===word[0])[0]
        let tmp = 1 
        for(let i = 1 ; i < word.length; i++){
            // 단어의 끝이거나 분기점이 있는경우 i번째까진 탐색해야함
            if(curNode.next.length !==1 || curNode.end) tmp = i+1 
            curNode = curNode.next.filter(v => v.val===word[i])[0]
        }
        if(curNode.next.length>0) tmp = word.length
        ret += tmp
    }
    return ret
}