[BOJ 5670, C++] 휴대폰 자판

https://www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

트라이 자료구조를 공부했는데, 다른 블로그에 나와있는 문자열 트리 그림을 확인해보면 코드 이해가 KMP보다 쉽습니다.

근데 소멸자 쓰는 건 자료구조 수업 이후에 처음이라 정신 나갈 뻔했네요.

 

 

 

1. 문제 풀이

---

문자열을 탐색한다는 내용과 문자열이 겹치면 자동으로 완성한다라는 내용을 통해 트라이 자료구조를 사용해야 한다는 것을 알 수 있습니다.

 

그리고 트라이 문제를 캐치할 수 있는 제일 큰 핵심은 똑같은 문자열은 들어오지 않는다와 입력값으로 들어오는 총 문자열의 길이가 특정값을 넘기지 않는 다는 것입니다. 왜냐하면 최악의 경우 한 글자마자 하나의 노드를 가질 수 있기 때문에 메모리가 터질 수도 있기 때문입니다.

그래서 다른 문제들을 살펴보니 입력값 총 문자열의 길이가 1,000,000을 넘지 않는다는 내용이 자주 보입니다.

 

이 문제는 기본적인 트라이 노드 구조체와 삽입 함수를 만들어주고, 추가적으로 문제의 답을 구하기 위한 함수를 만들어주면 됩니다.

 

트라이는 기본적으로 트리구조이므로 위 사진처럼 가지가 2개 이상으로 나뉘면 다음 재귀의 값은 (부모노드 값 + 1)로 설정합니다. 이후 문자열의 끝에 온다면 답에 저장해주면 됩니다. (3 + 2 + 2 + 1 = 8)

탑다운으로 푸는 방법도 있지만, 이게 더 직관적인 것 같네요.

 

이후에 메모리초과를 막기위해 delete 하는 것이 필요합니다.

---

 

 

 

2. 풀이 코드

---

#include <bits/stdc++.h>
using namespace std;
 
int n, m, t;
string s;
int ans;
 
struct Node {
    bool valid = false;
    Node* child[26];
    int branch = 0;
    Node() {
        fill(child, child + 26, nullptr);
    }
    ~Node() {
        for (int i = 0; i < 26; i++) {
            if (child[i]) delete child[i];
        }
    }
 
    void insert(int idx) {
        if (idx == s.length()) {
            valid = true;
            branch++;
            return;
        }
 
        int x = s[idx] - 'a';
        if (!child[x]) {
            child[x] = new Node();
            branch++;
        }
        child[x]->insert(idx + 1);
    }
 
    void go(bool isRoot, int val) {
        if (valid) ans += val;
 
        for (int i = 0; i < 26; i++) {
            if (child[i]) child[i]->go(false, val + ((!isRoot && branch == 1) ? 0 : 1));
        }
        return;
    }
};
 
int main() {
    cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    while (cin >> n) {
        Node* root = new Node();
 
        ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> s;
            root->insert(0);
        }
 
        root->go(true, 0);
 
        printf("%.2f\n", (double)ans / n);
 
        delete root;
    }
 
    return 0;
}

---