전화번호 목록

문제

문제의 시간 복잡도

문제의 시간 복잡도는 n이 100만으로 $O(n)$이하의 시간복잡도로 풀이를 작성하여야 한다.

접근법

먼저 문제를 보고 처음든 접근법은 이중 for문을 돌면서 하나씩 확인을 하는 방법 이었다. 하지만 이경우에는 $O(n^2)$의 시간이 들기 때문에 내부 for문을 다른 알고리즘을 사용하거나 메모리를 사용하여 시간복잡도를 낮춰야 겠다는 생각을 했다.

그래서 생각을 한 것이 해시테이블 이었다. 이 문제에서 보면 n은 최대 100만 이지만 각 문자열의 길이는 20이하인것을 볼 수 있다. 이 부분을 보고 for문을 n만큼 돈 이후에 안에 for문에서 문자열만큼 도는 것은 어떨까 라는 생각을 하게 됐다.

그래서 먼저 for문을 n에 대해서 돌면서 해시테이블에 추가를 해주고, n에 대한 for문에서 각 요소 하나하나를 돌 때 문자열의 길이 만큼을 돌면서 해시테이블에 find 함수를 사용해주었다. 해시테이블의 find 함수는 상수시간안에서 해결이 되기 때문에 상수 시간안에 for문이 해결이 될것이라고 생각을 했다.

풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <cmath>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string,int> map;
    for(int i=0; i<phone_book.size() ;i++)
    {
        map.insert(make_pair(phone_book[i],1));
    }
    
    
    for(int i=0; i<phone_book.size();i++)
    {
        for(int j=0;j<phone_book[i].size();j++)
        {
            if(map.end() != map.find(phone_book[i].substr(0,j)))
            {
                return false;
            }
        }
    }
    return answer;
}