[프로그래머스] 전화번호 목록 문제풀이 c++

 

카테고리가 해시인걸 봐선 해시로 푸는 문제인듯하지만

정렬이 훨씬 빠를 것같아서 정렬로 문제를 풀었다.

phone_book을 정렬하면 인접한 데이터만 확인하면 접두사인지 확인할 수 있다.

따라서 정렬 후 phone_book을 탐색하여

phone_book.substr(0,x.size())와 x가 같다면(접두사)

answer를 false로 바꾸고 탐색을 종료하면 된다.

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    string x = phone_book[0];
    for(int i=1; i<phone_book.size(); i++){
        if(x.size()<=phone_book[i].size() && x==phone_book[i].substr(0,x.size())){
                answer = false;
                break;
        }
        else{
            x = phone_book[i];
        }
    }
    return answer;
}

 

unordered_map을 이용한 풀이도 해봤다.

map에 각 원소를 넣고,

phone_book을 전체탐색하여, phone_book[i]의 가능한 접두사를 다 확인하여

map에 해당 값이 있는지 확인하고, 있다면 answer를 false 바꾼다.

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string,int> m;
    for(string s:phone_book){
        m[s] = 1;
    }
    for(int i=0; i<phone_book.size(); i++){
        string x = "";
        for(int j=0; j<phone_book[i].size()-1; j++){
            x += phone_book[i][j];
            if(m.find(x) != m.end()){
                answer = false;
                break;
            }
        }
    }
    return answer;
}