[Programmers] Level2 : 전화번호 목록

Question

---

Solution

처음에 모든 번호에 대해 비교를 하기위해 이중for루프를 사용했더니 효율성 3,4에서 시간 초과가 되었다. 이 문제는 string에 대한 sort()에 대해 다시 생각해보게 되는 문제다.

• 전화번호는 string으로 이루어져 있다. 이를 정렬 시키면 사전순으로 정렬이된다.
• 사전순이기 때문에 for 루프로 i와 인접한 i+1을 i.size만큼 비교하면 된다.

---

Cord

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

using namespace std;

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

    // 길이가 큰 번호가 작은 번호의 접두어가 될 수 없다. (string 사전순 정렬)
    sort(phone_book.begin(), phone_book.end());

    // 작은 번호 i와 i+1의 size만큼 비교
    for (int i = 0; i < phone_book.size() - 1; ++i)
    {
        string temp = phone_book[i+1].substr(0, phone_book[i].size());

        if (phone_book[i] == temp) { return false; }
    }

    return answer;
}

// --------------------------------- 효율성 3,4 실패 -------------------------------------
bool solutionFail(vector<string> phone_book)
{
    bool answer = true;

    // 길이가 큰 번호가 작은 번호의 접두어가 될 수 없다. (size에 대한 오름차순 정렬)
    sort(phone_book.begin(), phone_book.end());

    // 작은 번호 i와 i의 size만큼 j에 대해 비교
    for (int i = 0; i < phone_book.size() - 1; ++i)
    {
        for (int j = i + 1; j < phone_book.size(); ++j)
        {
            string temp = phone_book[j].substr(0, phone_book[i].size());

            if (phone_book[i] == temp) { return false; }
        }
    }

    return answer;
}
// ----------------------------------------------------------------------------------------

---

Result