[알고리즘] 프로그래머스 - 전화번호 목록

문제설명
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.

풀이방법
1. 2중 for문을 돌려 j와 다른 i번째 번호들이 phone_book[j]의 앞부분과 같은지 확인한다.

개선방법
2중 for문을 사용하기 때문에 배열의 길이가 길때는 불필요한 작동이 많아진다
for문을 돌리기 전에 배열을 정렬하게되면 for문을 한번만 사용해도 된다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {
    
    for(int i = 0; i < phone_book.size(); i++){
        for(int j = 0; j < phone_book.size(); j++){
            if(i == j) continue;
            if(phone_book.at(j).substr(0, phone_book.at(i).size()) == phone_book.at(i)){
                return false;
            }
        }
    }
    
    return true;
}