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

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

 

접두어 즉 다른번호의 시작이 되는 번호가 있으면 false 없으면 true를 반환하는 문제이다. 그래서 길이 기준으로 sort하고 처음 접근할 때 반복문을 돌면서 앞의 단어의 길이만큼 substr해서 같은 단어가 있으면 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(); i++) {
        string check = phone_book[i];
        for (int j = i + 1; j < phone_book.size(); j++) {
            if (phone_book[j].substr(0, check.length()) == check) {
                return false;
            }
        }
    }

    return true;
}

 

 

하지만 효율성 3,4번에서 시간초과가 떠서 실패했다. for문이 2번 도는게 O(n^2)라서 시간초과가 뜬 것이다. 

그런데 sort 가 길이기준으로만 정렬해주는 줄알았는데 사전 기록 기준으로도 정렬을 해준다고 해서 그렇게 된다면 앞의 값과 그 뒤에 값이 사전 기록상으로 비슷한 원소가 오기 때문에 비교를 인접 원소만 해주면 된다고 한다!

 

고친버전

 

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

using namespace std;

bool solution(vector<string> phone_book) {

    sort(phone_book.begin(), phone_book.end());          //이렇게 정렬을 하면 사전순으로 정렬된다 즉 1 1 처럼  같은 숫자대로 정렬
    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 true;
}