[백준] 5670 휴대폰 자판

5670번: 휴대폰 자판

문제 확인

 

문자열 처리, 사전 검색 문제입니다.

사전 순으로 정렬하여 dfs 탐색으로 풀 수 있지만 간단하게 트라이 자료구조를 이용해서 풀 수 있습니다.

 

풀이

 

모든 입력을 트라이 자료구조에 삽입하고 현재 단어 위치에서 갈 수 있는 문자의 종류 개수를 count 변수로 둡니다.

count 변수를 활용해서 자동완성이 가능한지 여부를 구할 수 있습니다.

• count == 1 : 현재 위치에서 갈 수 있는 문자의 종류는 하나, 따라서 자동완성이 가능합니다.
• count > 1 : 갈 수 있는 문자의 수가 여러개이므로 자동완성이 불가능합니다.

 

한 가지 더 고려해야 할 점은 hell, hello처럼 끝에서 자동완성을 하면 안 되는 경우입니다. 이는 트라이 자료구조에서 사용하는 finish 변수를 통해 구할 수 있습니다.

c = 1; //조건에 따라 초기 문자는 필수로 입력되어야 함
for(index 1 ~ n - 1){
    if(종류 > 1 || 현재노드 finish == true) result++;
    cur_trie = cur_trie->next[ary[index] - 'a'];
}
	

 

코드

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
struct Trie {
    bool finish;    
    int count = 0;
    Trie* next[26];    
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }
    void insert(char* key) {
        int n = strlen(key);
        Trie* cur_node = this;
        for (int i = 0; i < n; i++) {
            int cur_idx = key[i] - 'a';
            if (cur_node->next[cur_idx] == NULL) {
                cur_node->count++;
                cur_node->next[cur_idx] = new Trie();
            }
            cur_node = cur_node->next[cur_idx];
        }
        cur_node->finish = true;
    }
    int find(char* key) {
        int n = strlen(key), c = 1;
        Trie* cur_node = next[key[0] - 'a'];
        for (int i = 1; i < n; i++) {
            if (cur_node->count > 1 || cur_node->finish) ++c;
            int cur_idx = key[i] - 'a';
            cur_node = cur_node->next[cur_idx];
        }
        return c;
    }
    
};
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(2);
    cout.setf(ios::fixed);
    char ary[100000][81];
    int n;
    while (cin >> n) {
        double t = 0;
 
        Trie trie;
        for (int i = 0; i < n; i++) 
            cin >> ary[i];
        for (int i = 0; i < n; i++)
            trie.insert(ary[i]);
        for (int i = 0; i < n; i++)
            t += trie.find(ary[i]);
        cout  << t / n << '\n';
    }
 
 
}