[프로그래머스] [3차] 자동완성 (js)

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

프로그래머스

문제 설명

자동완성
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
go
gone
guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
입력 형식
학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

출력 형식
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.
입출력 예제

words	result
["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.

 

나의 풀이 

// Trie의 노드 구조를 정의
class TrieNode {
    constructor() {
        this.children = {}; // 자식 노드들을 저장하는 객체
        this.count = 0;     // 현재 노드에서 시작하는 단어의 수를 저장
    }
}

// Trie 구조를 정의하는 클래스
class Trie {
    constructor() {
        this.root = new TrieNode(); // Trie의 루트 노드를 생성
    }
    
    // 단어를 Trie에 삽입하는 메서드
    insert(word) {
        let currentNode = this.root;
        for (let char of word) {
            // 현재 문자가 자식 노드에 없다면 새로운 TrieNode를 생성
            if (!currentNode.children[char]) {
                currentNode.children[char] = new TrieNode();
            }
            // 다음 노드로 이동
            currentNode = currentNode.children[char];
            currentNode.count++; // 노드의 count를 1 증가
        }
    }
    
    // 단어의 고유 접두사 길이를 반환하는 메서드
    getUniquePrefixLength(word) {
        let currentNode = this.root;
        let prefixLength = 0;
        
        for (let char of word) {
            currentNode = currentNode.children[char]; // 다음 노드로 이동
            prefixLength++; // 접두사 길이를 1 증가
            // 현재 노드의 count가 1인 경우, 유일한 접두사를 찾은 것
            if (currentNode.count === 1) {
                break;
            }
        }
        
        return prefixLength; // 접두사 길이를 반환
    }
}

// solution 함수는 주어진 단어 리스트로 Trie를 구축하고,
// 각 단어의 고유 접두사 길이의 합을 반환
function solution(words) {
    let trie = new Trie();
    let answer = 0;

    // 모든 단어를 Trie에 삽입
    for (let word of words) {
        trie.insert(word);
    }

    // 각 단어의 고유 접두사 길이를 누적하여 총 문자 수를 계산
    for (let word of words) {
        answer += trie.getUniquePrefixLength(word);
    }

    return answer; // 총 입력해야 할 문자 수 반환
}

 

처음 문제를 접했을 때 단어리스트를 돌면서 각 문자열을 비교해서 같은 문자가 있는지 비교하려고 했었는데 시간복잡도도 커지고 비효율적이라고 생각해 고민을 하던 중 Trie 알고리즘을 적용해서 풀면 된다는 것을 알게되었다. 

Trie 알고리즘은 처음 접해본 알고리즘이라 여러번 사용해보면서 익숙 해져야될 것 같다. 

(Trie는 문자열을 효율적으로 저장하고 탐색하기 위한 자료구조. 특히, 문자열 집합에서 공통 접두사를 가진 문자열을 관리하는 데 유리하며, 문자열 검색, 자동 완성, 사전 구현 등의 문제에 자주 사용)