Level 2. 전화번호 목록

Level 2. 전화번호 목록

 

 

길이 순으로 정렬한 후 앞에서부터 길이가 짧은 순으로 비교했다.

• 길이가 긴 문자열이 짧은 문자열의 접두어가 될 수는 없기 때문이다.

 

하지만, 이 풀이는 시간 초과가 발생한다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book)
{
    size_t size = phone_book.size();

    sort(phone_book.begin(), phone_book.end(), [](string a, string b) { return a.length() < b.length(); });

    for (int i = 0; i < size - 1; ++i)
        for (int j = i + 1; j < size; ++j)
            if (phone_book[j].find(phone_book[i]) == 0)
                return false;

    return true;
}

 

힌트에서 아이디어를 얻었다.

문자열이 어떻게 정렬되는지 잘 알고 있었다면 쉬운 문제였다.

 

문자열을 sort() 함수로 정렬하게 되면, 길이와 상관 없이 앞에서부터 아스키 순으로 앞에 오는 문자가 높은 우선순위를 갖는다.

• "112"보다 "20"이 우선순위가 높다.

 

그러므로 정렬되어 있는 경우라면, 자신 바로 뒤의 문자열의 접두어인지만 확인하면 된다.

• "119", "20", "11978" 같은 상황은 불가능하기 때문이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book)
{
    size_t size = phone_book.size();

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

    for (int i = 0; i < size - 1; ++i)
        if (phone_book[i + 1].find(phone_book[i]) == 0)
            return false;

    return true;
}

 

이 문제가 해시 카테고리에 있어서 해시로 푼 사람도 있었다.

 

내 첫 번째 풀이가 현재 문자열이 다른 문자열의 접두어인지 일일이 확인하는 방식이라면, 이 풀이는 해시 테이블을 사용해 현재 문자열을 두고 다른 문자열은 알아서 확인되는 방식이라고 할 수 있다.

 

마치 for문으로 순회하면서 결과를 찾는 것과, 델리게이트를 사용해 구독자가 누군지 신경 쓰지 않는 것과 비슷한 느낌이다.

 

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book)
{
    size_t size = phone_book.size();
    unordered_map<string, bool> umap;

    for (string& phone : phone_book)
        umap[phone] = true;

    for (string& phone : phone_book)
    {
        string t = "";

        for (char digit : phone)
        {
            t += digit;

            if (umap[t] && phone != t)
                return false;
        }
    }

    return true;
}