[프로그래머스 고득점Kit] 전화번호목록(해시) - c++

접근

처음에 문제를 보고 길이순으로 정렬한 다음에 비교하면 되겠다 라고 생각하고 코드를 짰다. 길이가 같으면 서로 같은 문자열은 없으므로 비교할 필요가 없으니 continue를 해주면 효율성을 충분히 고려하는거라고 생각했는데 정확성은 다 통과하지만 효율성 3, 4번을 통과하지 못했다.

오답코드

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

using namespace std;

bool compare(string a, string b){
    if(a.size()==b.size()){
        return false;
    } else {
        return a.size()<b.size();
    }
}

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end(), compare);
    for(int i=0;i<phone_book.size()-1;i++){
        int len=phone_book[i].size();
        for(int j=i+1;j<phone_book.size();j++){
            if(len==phone_book[j].size()) continue;
            if(phone_book[i]==phone_book[j].substr(0,len)){
                return false;
            }
        }
    }
    return true;
}

풀이

답은 사전순 정렬이었다. phone_book을 사전순으로 정렬한 뒤 i번째와 i+1번째만 비교한다. 사전순 정렬이기 때문에 i+1번째의 접두사가 i가 아닐경우 i+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()-1;i++){
        int len=phone_book[i].size();
        if(phone_book[i]==phone_book[i+1].substr(0,len)) return false;
    }
    return true;
}

 

여담

근데 왜 해시 카테고리에 있는지는 모르겠다. 해시를 사용한 풀이는 떠오르지 않는데...