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

문제

---

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

풀이

---

단순하게 sort로 정렬 후, loop문을 돌며 접두어인지 확인하여 해결할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

    sort(phone_book.begin(), phone_book.end());

    for (int i = 0; i < phone_book.size() - 1; i++)
    {
        if (phone_book[i].size() == phone_book[i + 1].size())
        {
            continue;
        }

        if (!phone_book[i + 1].find(phone_book[i]))
        {
            answer = false;
            return answer;
        }
        
    }

    return answer;
}

문제의 주제인 해시로 푸는 경우, 단어를 추출, 비교하여 정답을 구할 수 있다.

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

using namespace std;

bool solution(vector<string> phone_book)
{
    unordered_map<string, int> map;
    for (int i = 0; i < phone_book.size(); i++)
        map[phone_book[i]] = 1;

    for (int i = 0; i < phone_book.size(); i++)
    {
        for (int j = 0; j < phone_book[i].size() - 1; j++)
        {
            string phone_number = phone_book[i].substr(0, j + 1);
            
            if (map[phone_number]) return false;
        }
    }

    return true;
}