[JS] 가사 검색 (2020 KAKAO BLIND RECRUITMENT)

트리구조를 변형해서 해결하였다!!!

 

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

프로그래머스

 

 

생각할 거리가 많은 문제였다.

 

 

 

각 키워드 길이의 합이 백만개이므로 절대 일반적인 방법으로는 해결할 수 없다고 생각했다.

 

따라서 트리구조로 문제를 해결해보려했다.

 

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

위와같은 구조의 Node를 두고 next배열에는 다음 오는 배열이 나오도록 했다.

 

문제에서 예시를 둔 아래를 Node 트리로 만든다면

["frodo", "front", "frost", "frozen", "frame", "kakao"]

 

f  - r - o - d - o

              - n - t

              - s - t

              - z - e - n

        ㄴa - m - e

k - a - k - a - o

 

위와같은 형식으로 만들어낼 수 있다.

 

따라서 ?를 만난다면 재귀적으로 Next의 모든 값을 순회하고 그렇지 않으면 Next 배열 중에서 다음으로 오는 알파벳만 가져오는식으로 구현하려 했다.

 

허나 해당방식 역시 시간초과가 났다.. (?가 많은 경우 재귀 시 가짓수가 너무 많아지는 문제가 발생)

 

 

해당 부분의 해결책은 위 부분이다. ?가 처음에 오거나 끝에만 올 수 있다.

 

node.end에 해당 노드부터 시작해서 자식노드들의 개수를 저장해 놓는다면 굳이 모든 노드를 탐색하지 않아도 개수를 반환할 수 있다. 일종의 DP로 미리 자식노드의 갯수를 저장할 수 있다. 하지만 우리가 저장한 node는 앞에서 뒤로만 검사하므로 ?가 뒤에만 오는 경우만 감지할 수 있다.

 

따라서 ?가 앞에서 오는 경우를 탐지하기 위해 단어들을 거꾸로 둔 reverse배열을 두고 ?가 앞에있는지, 뒤에있는지에 따라 다르게 동작하도록 했다.

 

추가적으로 단어의 길이가 정확하게 일치해야 하는 부분이 있으므로 트리를 만들때 단어의 길이를 기준으로 트리를 만들어주었다.

 

f  - r - o - d - o

              - n - t

              - s - t

        ㄴa - m - e

k - a - k - a - o

f - r - o - z - e - n

 

즉 주어진 예제에서는 위와같이 3개의 트리가 나오게 된다.

 

 

 

+++

JS는 왜이렇게 재귀 제한이 짧은지 모르겠다... 자식노드들의 수를 저장하기 위해서 후위탐색을 해야하는데 재귀제한에 걸려 스택으로 구현해주었다. 스택으로 후위탐색 구현하는건 넘 귀찮다.

 

 

문제 자체는 단순하지만 해결방법은 쉽지않은 문제였다!

 

 

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

function solution(words, queries) {
    const map = new Map() //물음표가 뒤에 있는 경우를 위함
    const reverseMap = new Map() //물음표가 앞에 있는 경우를 위함
    
    //트리 구조로 단어 저장
    for(const word of words){
        const rootNode = map.has(word.length) ? map.get(word.length) : new Node("")
        if(!map.has(word.length)) map.set(word.length,rootNode)
            
        let node = rootNode
        for(let i = 0 ; i<word.length;i++ ){
            let nxNode = node.next.find(v=>v.val===word[i])
            if(!nxNode){
                nxNode = new Node(word[i])
                node.next.push(nxNode)
            }
            node = nxNode
        }
        node.end+=1
    }
    //거꾸로 단어도 저장
    for(const word of words){
        const rootNode = reverseMap.has(word.length) ? reverseMap.get(word.length) : new Node("")
        if(!reverseMap.has(word.length)) reverseMap.set(word.length,rootNode)
            
        let node = rootNode
        for(let i = word.length-1 ; i>=0 ;i--){
            let nxNode = node.next.find(v=>v.val===word[i])
            if(!nxNode){
                nxNode = new Node(word[i])
                node.next.push(nxNode)
            }
            node = nxNode
        }
        node.end+=1
    }
    //?가 나왔을때 갯수를 미리 저장해둠
    const dfs = (rootNode) => {
        const retNode = new Node("")
        const stk = [[rootNode,retNode,false]]
        
        while (stk.length){
            const [node,parent,isVisited] = stk.pop()
            if(!(node.next.length)) {
                parent.end += 1
                continue
            }
            if(isVisited){
                parent.end += node.end
                continue
            }
            
            stk.push([node,parent,true])
            for(const nxNode of node.next){
                stk.push([nxNode,node,false])
            }
            
        }
        
        return retNode.end
        
    }
    //정방향과 역방향 모두 개수 저장
    for(const [len,rootNode] of map){
        dfs(rootNode)
    }
    for(const [len,rootNode] of reverseMap){
        dfs(rootNode)
    }
    // word와 node로 문자 개수 계산
    const getCnt = (word,node) => {
        for(let i = 0 ; i < word.length ; i++){
            const st = word[i]
            if(st==='?') {
                return node.end
            }
            const nxNode = node.next.find(v => v.val===st)
            if(!nxNode) return 0
            node = nxNode
        }
        return node.end
    }
    
    //?가 앞에있다면 역방향, ?가 뒤에있다면 정방향으로 검사
    return queries.map(querie => {
        const rootMap = querie[querie.length-1]==='?' ? map : reverseMap 
        if(querie[querie.length-1]!=='?') querie = [...querie].reverse().join('')
        const rootNode = rootMap.get(querie.length)
        if(!rootNode) return 0
        return getCnt(querie,rootNode)
    })
    
    
    
}