[C++] Programmers [3차] 자동완성 (2018 KAKAO BLIND RECRUITMENT)

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

코딩테스트 연습 - [3차] 자동완성

해당 문제는 문제 자체가 어려웠다기 보다는 c++에서의 String처리가 낯설었다. String은 C언어로 보면 literal이기 때문에 변경이 불가능한 문자열이다. char[] 처럼 포인트 접근을 하기 위해서는 형변환이 필요했고, 이 때 형변환은 단순히 char가 아니라 변경이 불가능한 const char로 변경해야한다.

#include <string>
#include <vector>

using namespace std;

typedef struct node {
    int cnt;  // The number of words which 
    struct node* link[26] = {NULL,};
} NODE;


void Insert(const char *str, NODE* node) {
    
    if (*str=='\0') {
        return;
    } 
    
    int idx = *str - 'a';
    if (node->link[idx] == NULL) {
        NODE *temp = new NODE();
        node->link[idx] = temp;
    }
    node->link[idx]->cnt++;
    Insert(str+1, node->link[idx]);
}

/*
void Print(NODE* node) {
    
    for (int i= 0; i< 26; i++) {
        if (node->link[i] != NULL) {
            printf("[%c] %d\n", i+'a', node->link[i]->cnt);
            Print(node->link[i]);
        }
    }
    
}
*/

int Calculate(const char* str, NODE *node, int count) {
    if (node->cnt == 1 || *str == '\0') return count;
 
    int idx = *str - 'a';
    return Calculate(str + 1, node->link[idx], count + 1);
}

int solution(vector<string> words) {
    int answer = 0;

    NODE *root = new NODE();

    // Initialize
    for (int i =0; i< words.size(); i++) {
        const char *word= words[i].c_str();
        Insert(word, root);
    }
    
    /*
    for (int i = 0; i < 26; i++) {
        if (root->link[i]!=NULL) {
            printf("%d", root->link[i]->cnt);
        }
    }   
    */
    
    // Start searching
    for (int i =0; i< words.size(); i++) {
        const char *word= words[i].c_str();
        answer += Calculate(word, root, 0);
    }
    
    return answer;
}

 

알고리즘 자체는 간단하다. 주어진 단어를 기본적으로 Trie(트라이) 구조로 모두 저장한다. Trie의 Node는 int형 변수 하나와 Node 26개 포인트로 이루어진 구조체이다. (26개인 이유는 알파벳의 개수가 26개이기 때문이다. 만약 개수를 지정하는 것이 싫다면 map형태를 이용해도 될 듯하다.) 단어를 Trie형태로 저장하면서 Node에 존재하는 int형 변수를 +1 해준다. 만약 Node에 존재하는 숫자가 1이면 경우의 수는 하나밖에 없다는 의미이므로 단어가 정해진다. 즉, 자동완성이 가능한 경우는 Node의 int형 변수가 1일 경우이며 끝까지 1이 안나오면 단어를 끝까지 쳐야함을 의미한다.