[백준 5670][💚4] 휴대폰 자판 (트라이, 원하는만큼 입력 받기)

🚀 난이도

💚 플래티넘 4

🚀 문제

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

🚀 내 풀이 ⭕

트라이에 관한 더 자세한 설명은 이 포스트를 참고해주세요. 👉 (C++) 문자열 집합 : 트라이 자료구조

• 1️⃣ 첫 글자는 자동 입력 할 수 없다. 무조건 사용자가 수동 입력 해야 한다.
• 2️⃣ 다음 글자가 될 수 있는 후보가 유일하게 하나일 때만 자동 입력이 될 수 있다. (다음 글자가 없거나 있거나 이렇게 갈리는 경우도 자동 입력이 안됨)

---

• 현재 문자의 자식 문자가 없다면 👉 문자열의 끝이므로 입력 자체를 더 이상 안해도 된다. + 0
• 현재 문자의 자식 문자가 있다면
  • 자식 문자의 개수가 1 개 일 때 (즉, 자식 서브트리가 오직 한 개) 👉 자동 입력 가능하다. + 0
  • 자식 문자의 개수가 2 개 이상일 때 👉 수동 입력 해야 한다. + 1

만들어놓은 트라이 트리를 순회하면서 현재 방문중인 노드(문자)를 기준으로 자식 문자의 개수를 따져 버튼을 수동으로 눌러야 하는 (수동 입력) 횟수를 누적 합하면 된다. 첫 문자는 무조건 수동 입력을 해야 하기 때문에 count 값은 1 에서 시작하고, 트라이 트리의 루트가 아닌, 첫 문자 노드부터 순회 시작하면 된다.

---

입력에 있어 (N + 문자열들) 을 한 세트라고 한다면, 이 문제는 특이한게 총 몇 세트를 입력할지가 주어지지 않았다. 즉, 그냥 입력이 주어진대로 입력을 해야 하는 것이다.

이에 대한 반복 조건을 while(cin >> n) 로 해주면 된다. 즉, 입력 받은만큼 동안 반복문을 돌리는 것이다. 즉, n에 입력할 수 있는게 더 이상 없으면 while 문이 종료 될 것이다.

istream 타입의 cin 객체의 >> 연산인 cin >> 는 cin 객체를 리턴하는데, 형변환 연산자 오버로딩도 되어 있어 결과적으로 입력에 성공하면 true 를, 실패하면 false 를 리턴하게 되는 듯 하다.

https://stackoverflow.com/questions/6791520/if-cin-x-why-can-you-use-that-condition

#include <bits/stdc++.h>

using namespace std;

class Trie {
private:
    bool isEnd;  // 단어의 끝인지 여부
    unordered_map<char, Trie*> child; // 자식 링크들을 담은 해시 맵  Key : 자식 문자(다음 글자)  Value : 자식 객체 주소
public:
    /* 트라이 만들기 */
    void Insert(string str) {
        Trie* now = this;
        for (int i = 0; i < str.length(); ++i) {
            if (now->child[str[i]] == nullptr)
                now->child[str[i]] = new Trie();
            now = now->child[str[i]];
            
            if (i == str.length() - 1)
                now->isEnd = true;
        }
    }
    /* 버튼 직접 수동으로 눌러야 하는 개수 */
    int AutoComplete(string str) {
        int count = 1; // 모든 첫 문자들은 무조건 입력해야하니.. 1 에서 시작
        Trie* now = child[str[0]]; // 루트 말고 첫 문자에서 시작하기
        for (int i = 1; i < str.length(); ++i) { 
            if (now->isEnd || now->child.size() > 1) // 현재 문자가 끝이거나 혹은 현재 문자의 자식 문자 개수가 2 이상이라면 수동으로 입력해야 한다. count += 1
                count++;
            now = now->child[str[i]]; // 다음 자식으로 타고 내려가기
        }
        return count; 
    }
};

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    while (cin >> n) {  // 원하는 만큼 입력 받기!! 
        vector<string> words(n);
        for (int i = 0; i < n; ++i)
            cin >> words[i];
        
        // 트라이 만들기
        Trie* root = new Trie();
        for (int i = 0; i < n; ++i)
            root->Insert(words[i]);

        // 모든 입력 횟수 합
        int sum = 0;
        for (int i = 0; i < n; ++i)
            sum += root->AutoComplete(words[i]);
        
        double result = (double)sum / words.size();
        cout << fixed << setprecision(2) << result << '\n'; // 출력 정밀도 2 자리로 설정
    }
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기