C++:: 프로그래머스 <전화번호 목록>

처음에 짠 코드는 효율성 테스트에서 시간초과 실패가 되었다. 단순히 이중 for문을 통한 코드이다.

#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book)
{
    int n = phone_book.size();
    sort(phone_book.begin(), phone_book.end());
    for(int i=0;i<n;i++)
    {
        int len = phone_book[i].size();
        for(int j=i+1;j<n;j++)
        {
            if(len == phone_book[j].size()) continue;
            if(!strncmp(phone_book[i].c_str(), phone_book[j].c_str(), len)) return false;
        }
    }
    return true;
}

map을 사용하여 구현한 풀이는 효율성 테스트에서 통과하였다.

#include <string>
#include <vector>
#include <map>
using namespace std;

bool solution(vector<string> phone_book)
{
    map<string,int> m;
    for(int i=0;i<phone_book.size();i++) m[phone_book[i]]++;//맵에 넣고
    for(int i=0;i<phone_book.size();i++)
        for(int j=1;j<phone_book[i].size();j++)
            if(m[phone_book[i].substr(0,j)]) return false;
	// phone_book의 접두사를 하나씩 넣어보면서 map에 들어있으면 false 리턴
    /*	예시
    	phone_book[0] = "123" 이면
        map에 "1", "12"를 넣어서 체크
    */
    return true;
}