[Algorithm] 해커랭크 - Hash Tables: Ransom Note

https://www.hackerrank.com/challenges/ctci-ransom-note/problem

한 납치범이 몸값을 요구하는 편지를 작성하기 위해 주어진 잡지의 단어를 오려내고자 하는데, 원하는 편지를 주어진 잡지의 단어만으로 작성할 수 있는지 답을 내는 문제다.

생각난 방법은 다음과 같다.

1. 이중 for문을 통해 전수조사

2. 해시 자료구조를 통해 O(n)의 시간으로 조사 (n : ransom-note의 단어 갯수)

1번 방법은 주어진 벡터 2개를 받아 일일히 검사하고, 같은 단어가 나올 때 마다 magazine 벡터에서 해당 원소를 제거하는 방식으로 알고리즘을 구현하였다. 

bool ransom_note(vector<string> magazine, vector<string> ransom) {
    int mSize = magazine.size();
    int ransomNumber = 0;
    for(int r_i=0; r_i<ransom.size();r_i++)
    {
        for(int m_i=0; m_i<magazine.size();m_i++)
        {
            if(ransom[r_i].compare(magazine[m_i])==0)
            {
                magazine.erase(magazine.begin()+m_i);
                ransomNumber++;
                break;
            }
        }
    }
    return (ransomNumber==ransom.size())?true:false;
}

다만 이 방법으로 동작시키면 Time Out이 나와 절반정도의 Test case가 Fail이 나온다.

2번 방법은 unordered_map을 이용했다.

pair<string, int> 를 저장하는 map을 선언한다. 이때 string : word<key>, int : 해당 word의 갯수<value> 가 된다.

unordered_map에 내장된 find() 메소드를 이용해 검색한 다음 값이 있으면 value를 체크하는 방식으로 구현하였다.

bool ransom_note(unordered_map<std::string,int> magazine,
 vector<string> ransom, int n) {
    int cuttedWordsNumber = 0;
    for(int i = 0; i < n; i++)
    {
        if(magazine.find(ransom[i]) != magazine.end())
        {
            if(magazine.find(ransom[i])->second > 0)
            {
                magazine.find(ransom[i])->second
                     = magazine.find(ransom[i])->second - 1;
                cuttedWordsNumber++;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
    return cuttedWordsNumber==n?true:false;
}

* 코드 작성 중 문제점

 전수조사 방법으로 인해 타임아웃이 발생하였다.

 해시 자료구조를 사용하는 방법을 몰라 검색하여 사용하였다.