백준 5670 c++ 휴대폰자판 // 트라이 자식수, 소수점출력방법, mx설정방법

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

1. mx설정방법

1. 그냥 문제에 있는 단어길이의 총합을 mx로 잡으면 된다.

n * 단어의 길이 -> 시간초과 난다...

각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 10^6이다.

 

2. 소수점출력방법

    cout << fixed;
    cout.precision(2); //!소수 둘째자리까지출력 (셋째에서 반올림)!

하면된다.

 

3. 트라이 자식수(의사코드)

1. insert 하면서 cnt를 +1 하면서 지나감 // cnt가 1임 -> 유일값

2. 값이 -1이면, child를 +1 한다. // 자식수를 기록해놓는다.

3. 삽입마지막단계에 chk배열로 단어의 끝을 표시한다.

* find ( root의 자식 부터 시작하므로 ret=1부터 시작)

0. !! ret+1은 다음단어를 입력받는다는 뜻이다. !!

1. cnt가 1이면 유일값이므로 그대로 종료

2. 자식이 1개 -> 자식 자동완성, ret+1안함 

2.1 . 단, 단어의 끝에서는 자식이 1개이더라도 다음자식을 입력받아야한다.

(ex. hell까지 입력한 경우 o를 입력할지 안할지 모름) // 디버깅과정에서 발견함

3. 다음단어를 입력하려고했으나(ret+1), 다음단어가 없는경우 ret-1로 복원해준다. (ex. find(hello)에서 o까지 온경우))

 

**개선 :

// 현재 문자가 끝이거나 혹은 현재 문자의 자식 문자 개수가 2 이상이라면 수동으로 입력해야(ret+1) 한다.

위와 같이 개선 가능할것 같다.

내코드의 대우명제인데??

if (!chk[cur] && child[cur] == 1) {

 

4. 전체코드

#include <bits/stdc++.h>

int root = 1;
int unused = 2;
const int mx = 100000 * 10 + 1; //!const 해야 배열의 크기로 사용가능!
int nxt[mx][26]; //종류
int cnt[mx], chk[mx], child[mx]; // 중복접두사의 갯수
int n;

using namespace std;

//내가 처음이면 1 리턴
void insert(string& s) {
    int cur = root;
    for (auto c : s) {
        if (nxt[cur][c - 'a'] == -1) {
            nxt[cur][c - 'a'] = unused++;
            child[cur]++;
        }
        cur = nxt[cur][c - 'a'];
        cnt[cur]++;
    }
    chk[cur] = 1; //단어의끝 표시
}


//전통적인 find : 있는지 없는지 검사
int find(string& s) {
    int ret = 1;
    int cur = root;

    for (int i = 0; i < s.size();++i) {

        /*if (nxt[cur][c - 'a'] == -1) {
            return false;
        }*/ //존재하는단어만 입력으로 들어옴!
        cur = nxt[cur][s[i] - 'a'];
        //cout << s[i] <<" "<< cnt[cur] << " " << child[cur] ;
        if (cnt[cur] == 1) {
            //cout << " 유일->모두자동완성 ";
            return ret; //유일한경우
        }
        //자식이1개다? -> 자동완성 -> ret+안하고 다음문자열 검색함
        if (!chk[cur] && child[cur] == 1) {
            //cout << " 자식이1명->자식자동완성 \n";

            continue; //자식이1명임 -> 자동완성
        }
        //단, 단어의끝은 예외(입력해야함)
        ret++;
        //cout << "다음단어를 입력하셈 ret+1 \n";
        if (i == s.size() - 1) {
            //cout << "다음단어 없으셈 \n";
            ret--;
        }
    }
    return  ret;

}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << fixed;
    cout.precision(2); //!소수 둘째자리까지출력 (셋째에서 반올림)!

    while (cin >> n) {
        root = 1;
        unused = 2;
        memset(nxt, -1, sizeof(nxt));
        fill(child, child + mx, 0);
        fill(chk, chk + mx, 0);
        fill(cnt, cnt + mx, 0);

        vector<string> v;
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            insert(s);
            v.push_back(s);
        }

        double ans = 0;
        for (int i = 0; i < n; ++i) {
            //ans+=find(v[i]);
            int t = find(v[i]);
            //cout << "답 "<<t << "\n";
            ans += t;
        }
        cout << 1.0 * ans / n<<"\n";
    }
    return 0;

}