[BOJ] 휴대폰 자판(5070)

[백준(BOJ)] 휴대폰 자판(5070) C++

문제 : BOJ_5070번 휴대폰 자판

문제 설명

Trie(트라이)

트라이로 해결하는 문제입니다.

입력한 문자열 다음의 문자가 저장된 문자열 중 하나밖에 없을 경우 자동으로 입력해 주고,

다음의 문자열이 하나 이상이거나, 입력을 멈출 때는 사용자가 입력을 해주어야 합니다.

이때 모든 문자에서 사용자가 입력해야 하는 입력의 평균 횟수를 구해야 합니다.

---

Solution

우선 기존 트라이의 공식을 이용해서 트라이 구조체 안에 모든 문자열을 넣어줍니다.

그 뒤에 각 문자열마다 한 번씩 for문을 돌리며 입력해야 하는 횟수를 저장합니다.

저장된 다음 문자가 2개 이상이거나, 끝나는 문자열일 경우 횟수를 저장합니다.

이때, 문제의 조건에서 처음에는 반드시 1회 문자를 입력해야 하므로, 항상 첫 문자에서 횟수가 1이 더해져야 하는데, 모든 문자열의 첫 글자가 같을 시에는 1이 더해지지 않으므로, 그 경우만 따로 횟수를 1씩 더해주면 됩니다.

---

Description

1. 테스트 케이스의 수가 지정되지 않음으로 EOF를 사용해야 합니다. (while (scanf("%d",&N) != EOF))
   
2. char word[100001][81]는 할당 크기가 크므로 지역변수가 아닌 전역변수로 선언합니다.
   
3. 테스트 케이스가 쌓일 수 있으므로, Trie를 삭제해 주어야 합니다.(delete trie)
   
4. 모든 문자열의 첫 문자가 같은 경우엔 전체 개수에서 N을 더해주었습니다.
   

---

#include <iostream>
using namespace std;
struct Trie {
    Trie* childTrie[26];
    bool isWord;
    int childCnt;
    Trie() {
        for (int i = 0; i < 26; i++) childTrie[i] = nullptr;
        isWord = false;
        childCnt = 0;
    }
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (childTrie[i]) delete childTrie[i];
        }
    }
    void insert(char* word) {
        if (*word == '\0') {
            isWord = true;
            return;
        }
        int nextNum = *word - 'a';
        if (childTrie[nextNum] == NULL) {
            childTrie[nextNum] = new Trie();
            childCnt++;
        }
        childTrie[nextNum]->insert(word + 1);
    }
    int check(char* word, int cnt) {
        if (*word == '\0') return cnt;
        if (childCnt > 1 || isWord) cnt++;
        int nextNum = *word - 'a';
        return childTrie[nextNum]->check(word + 1, cnt);
    }
};
int N;
char word[100001][81];
// 전역변수로 선언 (사이즈가 크므로)
int main(void) {
    while (scanf("%d",&N) != EOF) {
        // EOF 사용
        Trie* trie = new Trie();
        for (int i = 0; i < N; i++) {
            scanf("%s", word[i]);
            trie->insert(word[i]);
        }
        int result = 0;
        if (trie->childCnt == 1) result += N;
        // 전체 문자열의 첫 글자가 같은 경우 N 더해주기
        for (int i = 0; i < N; i++) {
            result += trie->check(word[i],0);
        }
        printf("%.2f\n", (double)result / N);
        delete trie;
        // 삭제
    }
    return 0;
}