[프로그래머스/c++] Lv2 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

효율성을 생각하면서 풀어야한다. phone_book의 길이가 최대  1,000,000이기 때문에 2중 for문을 사용하게 되면 시간초과가 난다.

 

바로 아래 코드는 2중 for문을 사용하지 않고 푼 코드이다.

접두사가 되기 위해서는 보통 길이가 짧은 string이 확률이 높다. 그렇기 때문에 정렬을 한 후 바로 다음 string이랑 비교를 해준다. 

 

map으로 푸는 방법도 있는데..더 공부해야될 것 같다. 

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

    return answer;
}

 

아래 코드는 시간 초과 되는 코드이다..정답은 맞지만 효율성에서 탈락 ㅜ

#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++){
        int iSize=phone_book[i].size();
        for(int j=i+1;j<phone_book.size();j++){
            string str=phone_book[j];
            if(phone_book[i]==str.substr(0,iSize)){
                answer=false;
                break;
            }
        }
    }
    
    return answer;
}