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

풀이

여러 개의 전화번호 목록들이 있을 때, 한 전화번호가 다른 전화번호의 접두어와 똑같다면 false를 리턴하고, 아니라면 true를 리턴하면 된다.

 

전화번호의 목록의 크기가 최대 100만이므로, 2중 포문은 안될 것 같고, 더 빠른 방법을 찾던 도중에 정렬을 하면 편하게 비슷한 숫자들끼리 뭉쳐있어서 양 옆의 비교가 가능할 것 같았다.

 

전화번호의 목록들을 일단 정렬한 다음에 앞의 전화번호에서 뒤의 전화번호의 접두어만 비교해서 같으면 false를 리턴하게 하고, 그러한 부분이 없다면 true를 리턴하면 된다.

#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++) {
        string previous = phone_book[i];
        string current = phone_book[i+1].substr(0, previous.size());
        if(previous == current) 
            return false;
    }
    return true;
}