[프로그래머스/Lv2] - 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

• 해시를 활용하여 문제를 해결해야 한다.
• 실제로는 꼭 해시를 활용하지 않아도 해결이 가능하다고 한다.
• 문제 풀이또한 주관적인 생각으로는 해시라고 하기보다 c++ 에서 unorder_map<>을 활용할 줄 아는 것이 필요하다고 생각한다.
• 처음에는 phone_book의 모든 요소를 unordered_map의 key로 등록하고 unordered_map을 iterator를 활용하여 loop를 수행하였으나 효율성 테스트 3,4 번에서 시간초과가 발생하여 아래와 같이 phone_book 요소를 subStr()으로 나눠서 unordered_map<>::find()를 사용하였다.

---

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) 
{
    bool answer = true;

    unordered_map<string, string> pbMap;
    vector<string>::iterator srcIter = phone_book.begin();
    while (srcIter != phone_book.end())
    {
		pbMap.insert(make_pair((*srcIter), (*srcIter)));
        ++srcIter;
    }

    srcIter = phone_book.begin();
    while (srcIter != phone_book.end())
    {
        for (int idx = 1; idx < (*srcIter).size(); idx++)
        {
            string subStr = (*srcIter).substr(0, idx);
            if (pbMap.end() != pbMap.find(subStr))
                return false;
        }

        ++srcIter;
    }

    return answer;
}

int main()
{
    vector<string> phone_book = { "119", "1192" };
    bool answer = solution(phone_book);
    printf("%d\n", answer);

    return 0;
}