[Programmers] 전화번호 목록(Lv.2)(C++)

풀이 소요시간 : 20분

한 문자열이 다른 문자열의 접두어인 경우를 판별하는 문제다.

이 조건을 구현을 못하는 사람은 없을거고, 시간 복잡도를 해결하는 것이 문제의 핵심이다. 머리를 잘못 굴려서 시간을 조금 더 썼지만 핵심을 살펴보자.

사전순으로 정렬하면 사실 끝이다.

문자열을 sort 함수로 단순 사전순으로 정렬하면 어떤 일이 벌어질까? 사전순으로 다음의 문자열이 이전 문자열을 포함하거나 or 포함하지 않거나 둘 중 하나의 케이스다.

포함한다면? 다음 문자열의 길이는 이전 문자열보다 적어도 같거나 길다. 또한 str.find() == 0 이다.

포함하지 않는다면? 다음 문자열의 길이는 알 수 없다. 또한 str.find() == string::npos 이다.

위와 같은 조건만 이용한다면 시간 초과에 걸리지 않고 통과될 수 있다.

전체 코드

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


unordered_map<string, int> Map;


bool solution(vector<string> phone_book) {
    

    sort(phone_book.begin(), phone_book.end());
    
    for(int i = 0; i < phone_book.size(); i++)
    {
        string s = phone_book[i];
        int len = s.length();
        
        for(int j = i + 1; j < phone_book.size(); j++)
        {
            if(phone_book[j].length() < len) break;
            
            if(phone_book[j].find(s) == string::npos) break;
            
            if(phone_book[j].find(s) == 0) return false;
        }
    }
    
    return true;
    
}