백준 1620 : 나는야 포켓몬 마스터 이다솜

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

1620번: 나는야 포켓몬 마스터 이다솜

 

정신나간 푸키먼 문제

 

어디서 만든걸 번역해온듯 한데

 

뭐 아무튼 해시 or 맵으로 간단하게 풀수있다.

 

다만 입력값이 100000개를 넘다 보니

io에 대해서 대비해놔야 한다

 

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
 
int N, M;
std::unordered_map<std::string, int> pokeHash;
std::vector<std::string> pokeVec;
 
void input()
{
    std::cin >> N >> M;
    pokeVec = std::vector<std::string>(N + 1);
    pokeHash.reserve(N + 1);
    std::string strInput;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> strInput;
        pokeHash[strInput] = i;
        pokeVec[i] = strInput;
    }
}
 
void solve()
{
    std::string input;
    for (int i = 0; i < M; ++i)
    {
        std::cin >> input;
        int pokeNum = std::atoi(input.c_str());
        if (pokeNum == 0)
        {
            std::cout << pokeHash[input];
        }
        else if (pokeNum <= N)
        {
            std::cout << pokeVec[pokeNum];
        }
        std::cout << '\n';
    }
}
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    input();
    solve();
    return 0;
}

 

이걸 트라이로 푼다면 속도면에서는 통과가 가능하나

 

100000개의 단어별로 메모리를 확보해놓아야 한다.

 

메모리 초과가 뜨니 트라이 사용엔 유의할것

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
 
struct Trie
{
    Trie()
    {
        //memset(next, 0, sizeof(next));
        for (int i = 0; i < 26; ++i)
        {
            next[i] = nullptr;
        }
    }
    ~Trie()
    {
        for (int i = 0; i < 26; ++i)
        {
            if (next[i])
            {
                delete next[i];
            }
        }
    }
 
    void insert(const char* word, const int num)
    {
        if (*word == '\0')
        {
            _num = num;
            return;
        }
 
        int idx = *word - 'a';
        if (next[idx] == nullptr)
        {
            next[idx] = new Trie;
        }
        next[idx]->insert(word + 1, num);
    }
 
    unsigned int find_num(const char* word)
    {
        if (*word == '\0')
        {
            return _num;
        }
        if (next[word[0] - 'a'] == nullptr)
        {
            return 0;
        }
 
        return next[word[0] - 'a']->find_num(word + 1);
    }
 
public:
    Trie* next[26];
    unsigned int _num = 0;
};
 
Trie trieArr;
 
int N, M;
std::vector<std::string> pokeVec;
 
void input()
{
    std::cin >> N >> M;
    pokeVec = std::vector<std::string>(N + 1);
    std::string strInput;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> strInput;
        pokeVec[i] = strInput;
        strInput[0] = strInput[0] - 'A' + 'a';
        trieArr.insert(strInput.c_str(), i);
    }
}
 
void solve()
{
    std::string input;
    for (int i = 0; i < M; ++i)
    {
        std::cin >> input;
        int pokeNum = std::atoi(input.c_str());
        input[0] = input[0] - 'A' + 'a';
        if (pokeNum == 0)
        {
            std::cout << trieArr.find_num(input.c_str());
        }
        else if (pokeNum <= N)
        {
            std::cout << pokeVec[pokeNum];
        }
        std::cout << '\n';
    }
}
 
int main()
{
    input();
    solve();
    return 0;
}

 

100000개의 단어, 길이별로 26개씩 할당을 하는데 이게 저마다 죄다 다른 단어면 메모리를 그만큼 많이 할당하니

 

문제가 생길 여지가 높다. 메모리 파악하는 눈치도 좀 키워야할텐데

 

일단 cin.tie 등과 같은 FastIO를 사용하면 된다.

 

혹은 scanf printf만 쓰거나