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

문제 링크

전화번호 목록

 

풀이

해시 문제라고 했는데 정렬로 풀었다.

1. a 번호가 b 번호의 접두어라고 한다면, 정렬을 했을 때 반드시 a 번호가 b 번호 앞에 나오게 된다.
2. 임시 string인 tmp에는 접두어라고 가정할 번호를 넣는다.
   1. tmp가 비어있으면 tmp를 해당 번호로 갱신.
   2. 해당 번호에서 접두어를 뽑았는데 tmp와 같지 않아도 갱신.
   3. 같으면 해당 번호는 tmp를 접두어로 가진다는 것을 의미하므로 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 tmp = "";
    for(int i=0;i<phone_book.size();i++)
    {
        if(tmp == "" || phone_book[i].substr(0, tmp.size()) != tmp)
        {
            tmp = phone_book[i];
        }
        else
        {
            answer = false;
            break;
        }
    }

    return answer;
}