글 읽기 - c++ 입력 받기 도와주세요..

euphoric_n 2년 전 0

5670번 휴대폰 자판 문제입니다.

트라이를 이용해 모든 문자열을 추가하고 탐색하면서 자판을 몇번 눌러야 하는지 체크합니다.

해당 문제 질문게시판을 확인했을때 입력 문제가 있어 수정했는데도 불구하고 50%에서 WA를 받습니다.

테스트케이스로는 문제 출처가 되는 대회 ICPC Latin America Regional Contests 2012의 테스트 케이스를 사용했고 이상 없었습니다.

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <iomanip>

#include <fstream>

// #define DEBUG
// #define FILE_DEBUG
#define FASTIO

class Trie {
    public:
    bool finish;
    char cur_ch;
    bool is_root;
    std::map<char, Trie> next;
    Trie() {}
    Trie(char c) { cur_ch = c; is_root = false; }
    void insert(std::string word) {
        if(word.size() == 0) {
            finish = true;
            return;
        }
        if(next.find(word[0]) == next.end()) {
            next[word[0]] = Trie(word[0]);
        }
        next[word[0]].insert(word.substr(1, word.size()));
    }
    void print(int depth) {
        if(!is_root) std::cout << std::string(depth, ' ') << cur_ch << '\n';
        for(auto &item : next) item.second.print(depth+1);
    }
    int find(std::string word) {
        if(word.size() == 0 && finish) return 0;
        // 남은 단어가 없고 해당 위치에서 끝날때 : 탐색 끝
        if(is_root) {
        // 시작 위치일 때 : 첫 글자 입력
#ifdef DEBUG
            std::cout << "press " << word[0] << '\n';
#endif
            return 1+next[word[0]].find(word.substr(1, word.size()));
        }
        if(!finish && next.size() == 1) {
        // 현재 위치에서 끝나는 단어가 없고 다음 글자가 한 종류일 때 : 통과
#ifdef DEBUG
            std::cout << "auto " << word[0] << '\n';
#endif
            return next[word[0]].find(word.substr(1, word.size()));
        }
        // 이외의 경우에는 다음 글자를 입력한다.
#ifdef DEBUG
        std::cout << "press " << word[0] << '\n';
#endif
        return 1+next[word[0]].find(word.substr(1, word.size()));
    }
};

int main() {
#ifdef FASTIO
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
#endif
#ifdef FILE_DEBUG
    std::ifstream fin;
    fin.open("input.txt", std::ios::in);
    auto &is = fin;
#endif
#ifndef FILE_DEBUG
    auto &is = std::cin;
#endif
    int n;
    while(is >> n) {
        Trie t = Trie();
        t.is_root = true;
        std::vector<std::string> dict;
        for(int i=0; i<n; i++) {
            std::string str;
            is >> str;
            dict.push_back(str);
            t.insert(str);
        }
#ifdef DEBUG
        t.print(-1);
#endif
        double sum = 0.0;
        for(const auto &str : dict) {
            int result = t.find(str);
#ifdef DEBUG
            std::cout << "find(" << str << ") = " << result << '\n';
#endif
            sum += result;
        }
        std::cout << std::fixed << std::setprecision(2) << sum/dict.size() << '\n';
    }
    return 0;
}

euphoric_n 2년 전 0

새로 풀어서 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 입력 받기 도와주세요..

euphoric_n 2년 전 0

euphoric_n 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말