[C++] 프로그래머스 : 전화번호 목록

1. 벡터풀이

정렬하면 앞숫자 순으로 정렬된다

따라서 접두사인 경우 인접해있으니 인접한 원소끼리 비교하면 끝

 

2. 해시풀이

모든 번호를 map에 넣고 1을 값을 주어 존재를 표시

이 후 모든 번호에 대해 앞자리부터 한자리씩 더해가며 map에 존재하는지 비교하면 끝

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
//     int pSize = phone_book.size();
//     sort(phone_book.begin(), phone_book.end());
    
//     for(int i=0; i<pSize - 1; i++){
//         if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].length())){
//             return false;
//         }
//     }
   
    unordered_map <string, int> map;
    int pSize = phone_book.size();
    
    sort(phone_book.begin(), phone_book.end());
    
    for(string p : phone_book){
        map[p]++;
    }
    
    for(int i=0; i<pSize; i++){
        int pl = phone_book[i].length();
        string pn = "";
        for(int j=0; j<pl; j++){
            pn += phone_book[i][j];
            if(map[pn] >0 && pn != phone_book[i])
                return false;
        }
    }
    
    return answer;
}​