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

https://programmers.co.kr/learn/courses/30/lessons/42577

처음 접근

단순하게 2중 for문으로 하나가 다른 것의 접두사가 됐는지 확인했더니 시간초과 🥲

문제 풀이

핵심은 string 배열을 정렬한 후 , O(n)으로 각자 바로 뒤에거랑만 비교하면 된다!

["119", "97674223", "1195524421"]

일 경우, 정렬하면

119
1195524421
97674223

이러한 순서가 나온다! 앞 숫자가 일치할 때, 문자열 길이가 작은 순서대로 정렬되기 때문이다.

만약 119 1195324 1192345 의 순으로 현재가 다음다음 것의 접두어가 되면 어떡하지? (바로 다음이랑만 비교하니까) 생각해봤는데
어차피 1개만 찾으면 바로 멈추고 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());

    for(int i=0;i<phone_book.size()-1;i++){
        if(phone_book[i]==phone_book[i+1].substr(0,phone_book[i].size())) return false;
    }
    

    return answer;
}

바로 다음 문자랑 비교할 때는 다음 문자를 현재 문자의 사이즈로 앞부터 잘라주면 된다.
따라서 substr(0,phone_book[i].size()) 사용!