[C++] 5670번 휴대폰 자판 - 자료 구조, 문자열, 트리, 트라이

1. 문제

• 이 모듈은 사건 내에서 가능한 글자가 하나뿐이면 그 글자를 자동으로 입력한다.
  • 모듈이 단어의 첫 글자를 추론하지 않는다. 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력하여야 한다.
• 사건이 주어졌을 때, 이 모듈을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하시오.

<입력>

• 여러 개의 테스트 케이스로 주어져 있다.
• - 1 -   단어의 개수 $N(1\le N\le {10}^5)$
• - N개의 줄 -   1~80글자인 영어 소문자로만 이루어진 단어. 똑같은 단어가 2번 이상 주어지지 않는다. 각 테스트 케이스마다 주어진 단어의 길이의 총합은 최대 ${10}^6$이다.

<출력>

• 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력

2. 재정의

• 다음 글자가 하나로 결정될 경우 자동으로 입력될 때, 사전이 주어졌을 때 평균 입력 횟수를 출력하라.

3. 해결 방법

• 내 코드의 알고리즘은 trash이고, 더 좋은 코드를 발견하여 아래 코드를 참조 바란다.

4. 실수한 점, 개선할 점

• 구조식에 vector와 같은 컨베이너 벨트를 넣을 경우 동적 메모리이기 때문에 이를 많이 사용하면 메모리가 겹쳐져서 메모리 참조 오류가 발생하므로 고정적인 크기를 가진 자료형만 구조식에 넣을 수 있다.
• C++을 아직 잘 몰라서 왜 그런지는 잘 모르겠지만 구조체를 단순 delete 하는 것이 아닌 소멸자에 다른 변수들도 delete를 해주어야 메모리 초과가 발생하지 않는다.
• 'A'가 아닌 'a'를 빼주어야 메모리 참조 오류가 발생하지 않는다.

 

<코드>

#include <iostream>

using namespace std;
// <문제>
// 단어의 개수 N
int N;
// 눌러야 되는 총 횟수 typingCnt
int typingCnt;

char word[81];

struct TRIE {
    bool Finish, top;
    TRIE *Node[26];
    int branchCnt;
    TRIE() {
        Finish = top = false;
        for(int i=0; i<26; i++)
            Node[i] = NULL;
        branchCnt = 0;
    }
    ~TRIE() {
        for(int i=0; i<26; i++)
            delete Node[i];
    }
    
    void Insert(char *str) {
        //cout << str << '\n';
        if(*str == '\0') {
            Finish = true;
            return;
        }
        
        int Cur = *str - 'a';
        if(Node[Cur] == NULL) {
            Node[Cur] = new TRIE();
            branchCnt++;
        }
        Node[Cur]->Insert(str + 1);
    }
};

bool input(TRIE *Root) {
    // 초기화
    typingCnt = 0;
    
    // 테스트 케이스가 다 끝나면 끝
    if(!(cin >> N))
        return false;
    //cout << N << '\n';
    
    for(int i=0; i<N; i++) {
        cin >> word;
        Root->Insert(word);
    }
    
    return true;
}

void dfs(TRIE *no, int cnt) {
    if(!no->top) {
        if(no->Finish) {
            typingCnt += cnt;
            if(no->branchCnt > 0)
                cnt++;
        }
        // 만약 가지가 2개 이상이라면 cnt++
        else if(no->branchCnt > 1)
            cnt++;
    }
    else
        cnt++;
    //cout << typingCnt << '\n';
    
    for(int i=0; i<26; i++) {
        if(no->Node[i] != NULL)
            dfs(no->Node[i], cnt);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cout << fixed;
    cout.precision(2);
    
    while(1) {
        TRIE *Root = new TRIE();
        
        if(!input(Root))
            break;
        
        Root->top = true;
        dfs(Root, 0);
        cout << (double)typingCnt/N << '\n';
        
        delete Root;
    }
    
    return 0;
}

 

<자료구조 트라이>

https://yabmoons.tistory.com/379

[ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++)

 

<C++ test case 개수 모를 때>

https://scarlettb.tistory.com/69

C++ test case 입력 개수 모를 때 입력 받기

 

<C++ 클래스의 생성자 & 소멸자>

https://effectivesquid.tistory.com/entry/C%EC%9D%98-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%83%9D%EC%84%B1%EC%9E%90-%EC%86%8C%EB%A9%B8%EC%9E%90

C++의 클래스 생성자 & 소멸자

 

<문제 바로가기>

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

5670번: 휴대폰 자판

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.