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

문제 설명

전화번호가 들어있는 phone_book 배열이 주어진다. 이 배열 내의 원소들 중, 하나라도 다른 전화번호의 접두어인 것이 있다면 false를 return하라. (기본적으로는 true를 return하라)

 

입출력 예

만일 phone_book 배열이 ["119", "97674223", "1195524421"]라면,

119가 1195524421의 접두어이므로 false.

 

추가 예시로는;

["123","456","789"] true.
["12","123","1235","567","88"] false.

 

풀이

C++ 라이브러리에 있는 sort()를 string 배열에 사용하면 "사전순"으로 정렬된다는 사실로부터 풀이법을 떠올려냈다.

 

만일 phone_book 배열 내에, 다른 번호의 접두어인 어떤 번호가 존재한다면, sort()를 했을 시 무조건 인접하게 위치하도록 정렬된다. 

 

따라서 phone_book 배열을 정렬한 뒤, 인접한 원소들끼리만 서로의 접두어인지 확인하면 된다.

 

코드

#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++)
    {
        if (phone_book[i + 1].find(phone_book[i]) == 0)
            return false;
    }
    return true;
}