문제설명
전화번호부에 적힌 전화번호를 담은 배열 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;
}