(javascript) 자동완성

코딩테스트 연습 - [3차] 자동완성 | 프로그래머스 스쿨

프로그래머스

 

트라이를 사용하는 문제.

 

트라이가 뭔지는 설명하기 어렵다. 내가 이해한 개념을 설명하자면, 문자열을 fsm으로 나타낸 것이라고 할 수 있다. 주로 접두사 문제에 쓰인다.

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

자세히는 위키를 보자.

 

풀이

 trie 자료구조를 사용한다.

 먼저 입력된 문자열 배열 words를 통해 trie를 생성한다. 트라이의 각 노드는 객체로 구현했다.

 문자열의 문자를 하나씩 돌면서 트라이에 저장한다. 문자를 모두 순회했다면 문자열의 끝을 알 수 있도록 current[' '] = true; 를 통해 표시한다.

 다시 문자열 배열을 순회하면서 문제를 푼다.

 문자를 순회하며 trie를 탐색한다. 현재 노드의 자식이 둘 이상이라면 그 위치 last를 기록한다.

 문자 순회가 모두 끝났을 때, count === last라면 문자열을 모두 입력해야 한다. 따라서 answer += last를 한다.

 count !== last라면 last에서 한 글자를 더 입력해야한다. 따라서 answer += last + 1을 한다.

 

코드

function solution(words) {
    var answer = 0;
    var root = { ' ': true };
    for (var word of words) {
        var current = root;
        for (var c of word) {
            if (c in current) {
                current = current[c];
            } else {
                current[c] = {};
                current = current[c];
            }
        }
        current[' '] = true;
    }

    for (var word of words) {
        var current = root;
        var count = 0;
        var last = 0;
        for (var c of word) {
            current = current[c];
            count++;
            if (Object.keys(current).length !== 1) {
                last = count;
            }
        }
        if (last === count) answer += last;
        else answer += last + 1;
    }
    return answer;
}

 

결과

 

후기

 트라이 구조는 별로 구현해본적이 없었다. 트라이를 생성하는것 까지는 쉽게 해결했지만, 트라이를 탐색해 결과를 계산하는 과정에서 헷갈렸다.

 손으로 직접 트라이를 그려 눈으로 따라가며 조건문을 다듬었다.

 중요한 점은 1. 마지막으로 분기가 발생한 지점, 2. answer에 last를 더해야할지, last+1을 더해야할지 결정하는 과정이었다.