[프로그래머스] 자동완성

자동완성

코드

#include <string>
#include <vector>

#define ALPHABETS 26

using namespace std;

class Trie {
    int depth;
    int count;
    bool start;

    Trie* children[ALPHABETS];

    void init() {
        for (int i = 0; i < ALPHABETS; i++)
            children[i] = 0;
    }

public:
    Trie() : depth(0), count(0), start(true) {
        init();
    }

    Trie(int depth): depth(depth), count(0), start(false) {
        init();
    }

    ~Trie() {
        for (int i = 0; i < ALPHABETS; i++)
            delete children[i];
    }

    void insert(const char* key) {
        count++;

        if (*key == '\0') return;
        int next = *key - 'a';
        if (children[next] == 0) {
            children[next] = new Trie(depth + 1);
        }
        children[next]->insert(key + 1);
    }

    Trie* find(const char* key) {
        if ((count == 1 && !start) || (*key == '\0')) return this;

        int next = *key - 'a';
        if (children[next] == 0) return 0;
        return children[next]->find(key + 1);
    }

    int getDepth() {
        return depth;
    }
};

int solution(vector<string> words) {
    int answer = 0;
    int size = words.size();
    Trie trie;
    Trie* node;

    for (int i = 0; i < size; i++) {
        trie.insert(words[i].c_str());
    }

    for (int i = 0; i < size; i++) {
        node = trie.find(words[i].c_str());
        answer += node->getDepth();
    }

    return answer;
}

풀이

• Trie 자료구조에 각 노드에 얼마나 자식이 있는지 나타내는 count 멤버변수, 깊이가 얼마나 되는지 나타내는 depth 추가
• Trie 노드의 insert 호출시 count 증가
• Trie 생성시 현재 depth에서 1을 증가시켜 새로운 Trie 노드의 깊이 저장
• 단어를 찾을 때 Trie 노드의 자식이 1개이며 시작 노드가 아닐 경우 this 반환
• 반복문을 수행하며 모든 단어들을 Trie에 insert
• 반복문을 수행하며 모든 단어들을 Trie에서 find, 반환된 노드에서 getDepth를 호출하여 깊이를 answer에 더해줌

다른 방법

• 정렬 후 i번째 단어와 i - 1번째 단어, i + 1번째 단어와 비교하여 입력해야할 문자 개수 계산

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/17685