[Level 2][C++] 전화번호 목록

풀이 1 - 해시테이블 이용

#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
//전화번호 앞자리를 기준으로 해시 테이블에 정리한다.
    vector<vector<string>> hashT(10);
    
    for(int i=0; i<phone_book.size(); i++)
    {
        //전화번호 앞자리를 해시 키로 얻는다. 
        int key = phone_book[i].front()-'0';
        //비어 있으면 집어 넣는다.
        if(hashT[key].empty())
            hashT[key].push_back(phone_book[i]);
        else
        {
            for(int j=0; j<hashT[key].size(); j++)
            {
                for(int k=0; k<=hashT[key][j].length(); k++)
                {
                    //문자열 어느 하나 중 끝까지 같다면, false반환. 
                    if(k == hashT[key][j].length() || k==phone_book[i].length())
                        return false;
                    if(hashT[key][j][k] != phone_book[i][k])
                        break;
                }                  
            }
           //같은 게 없으면 해시 테이블에 넣는다.
            hashT[key].push_back(phone_book[i]);            
        }
    }
    return true;
}

 

풀이 2 - 정렬해서 푼다.

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

using namespace std; 

bool solution(vector<string> phone_book) { 

     sort(phone_book.begin(), phone_book.end()); //내림차순으로 정렬

     for(int i=0; i<phone_book.size(); i++)
     {
          //내림차순이니, 철자 수가 더 작은 애가 앞으로 온다. 다음 문자열이 앞 문자열이랑 같다면 false.
         //substr(a,b) 위치 a를 시작으로 b만큼 문자열을 추출한다.
          if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())
               return false;
     }
     return true;
}