프로그래머스 [Lv. 4] 가사 검색 {언어 : JavaScript}

문제 링크

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

코딩테스트 연습 - 가사 검색

정답 코드

function solution(words, queries) {
    const answer = [];
    class Node {
        constructor(name, count, len) {
            this.name = name;
            this.count = count;
            this.len = len;
            this.next = [];
        }
    }
    const frontRoot = new Node("root", 0, 0);
    for (const word of words) {
        const len = word.length;
        let curNode = frontRoot;
        for (let i = 0; i < len; i++) {
            let isFound = false;
            const a = word.at(i);
            for (const v of curNode.next) {
                if (v.name === a && v.len === len) {
                    curNode = v;
                    v.count++;
                    isFound = true;
                    break;
                }
            }
            if (!isFound) {
                const aNode = new Node(a, 1, len);
                curNode.next.push(aNode);
                curNode = aNode;
            }
        }
    }
    
    const backRoot = new Node("root", 0, 0);
    for (const word of words) {
        const len = word.length;
        let curNode = backRoot;
        for (let i = len-1; i > -1; i--) {
            let isFound = false;
            const a = word.at(i);
            for (const v of curNode.next) {
                if (v.name === a && v.len === len) {
                    curNode = v;
                    v.count++;
                    isFound = true;
                    break;
                }
            }
            if (!isFound) {
                const aNode = new Node(a, 1, len);
                curNode.next.push(aNode);
                curNode = aNode;
            }
        }
    }
    
    for (const word of queries) {
        // 만약 word의 앞이 ?로 시작한다면 backRoot
        // 아니면 frontRoot
        const len = word.length;
        let tmp = 0;
        if (word.at(0) === "?") {
            let curNode = backRoot;
            for (let i = len-1; i > -1; i--) {
                const a = word.at(i);
                let noHave = true;
                if (a === "?") {
                    // 현재 노드에서 다음으로 가는 것중 길이가 같은 것을 찾아서 count를 더한다.
                    for (const v of curNode.next) {
                        if (v.len === len) {
                            tmp += v.count;
                        }
                    }
                    break;
                } else {
                    for (const v of curNode.next) {
                        if (v.name === a && v.len === len) {
                            curNode = v;
                            noHave = false;
                            break;
                        }
                    }
                    if (noHave) {
                        break;
                    }
                }
            }
        } else {
            let curNode = frontRoot;
            for (let i = 0; i < len; i++) {
                const a = word.at(i);
                let noHave = true;
                if (a === "?") {
                    tmp += curNode.count;
                    break;
                } else {
                    for (const v of curNode.next) {
                        if (v.name === a && v.len === len) {
                            curNode = v;
                            noHave = false;
                            break;
                        }
                    }   
                    if (noHave) {
                        console.log("noHave")
                        break;
                    }
                }
            }
        }
        answer.push(tmp);
    }
    return answer;
}

풀이 방법

1. 트리 형태로 가사를 저장한다.
2. 앞에서부터 트리인 경우와 뒤에서부터 트리인 경우를 구분한다.
3. quries를 탐색하면서 각 쿼리의 첫 번째 글자가 "?"인지 확인한다.
   • "?"라면 뒤에서부터 확인해야 하므로 backRoot를 사용
   • 아니라면 frontRoot를 사용한다.
4. "?"가 나온 시점에서 tmp값을 구해준다.
   • backRoot에서는 물음표 이후(curNode.next) 알파벳 중 길이가 같은 것들을 tmp에 모두 더해준다.
   • frontRoot에서는 현재 (curNode)의 개수를 tmp에 더해준다.
5. 만약 탐색중 next에 없거나 "?"가 아니라면 반복문을 빠져나와 0을 push한다.
6. 모든 쿼리를 탐색하고 answer를 출력하면 끝!

느낀점

• 실수한 부분이 정확히 frontRoot일 때 tmp를 더하는 부분과 noHave를 판단하는 부분이다.
• 조금더 정밀하게 코딩해야할 필요를 느꼈고 바로 어떻게 풀지 떠올라서 다행이었던 문제다.
• 다익스트라도 다시 풀어보면 좋겠고 이런 class를 사용하여 트리구조로 문제를 푸는 것도 자주 풀어보면 좋겠다.