코딩테스트 : 전화번호 목록

해당 문제는 전화번호부 전화번호 중 한개라도 다른 전화번호의 접두사인 경우 false를 반환하는 문제이다.

핵심 방법
string의 find함수를 이용해 같은 단어가 존재하는지 찾아낸다. find함수를 string에 사용할 경우 아래의 방식으로 동작한다.

str.find(str1)
str : 타깃 문자열
str1 : 타깃 문자열에서 찾을 문자열
반환값 : 찾았으면 str1이 등장하는 첫 index 번호, 못 찾았으면 string::npos 반환

 

find 함수에 대한 자세한 설명은 아래 링크에 정리해두었다.

Find 함수와 자료구조 별 시간 복잡도

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true; // 기본적으로 true로 설정합니다.
    
    // 전화번호부를 정렬합니다.
    sort(phone_book.begin(), phone_book.end());
    
    // 인접한 전화번호를 비교합니다.
    for(int i = 0; i < phone_book.size() - 1; i++)
    {
        // 다음 번호가 현재 번호로 시작하는지 확인합니다.
        if(phone_book[i + 1].find(phone_book[i]) == 0)
            return false; // 접두사 관계가 있으면 false를 반환합니다.
    }
    
    return answer; // 접두사 관계가 없으면 true를 반환합니다.
}