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

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

프로그래머스

 

전체 코드

#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++)
    {
        bool flag=true;
        for(int j=0; j<phone_book[i].length(); j++)
        {
            if(phone_book[i][j]!=phone_book[i+1][j])
                flag=false;
        }
        if(flag==true)
            return false;
    }
    return answer;
}

 

풀이 방법

문자열을 사전식으로 정렬하여 i번째 문자열과 i+1번째 문자열에 대해 비교만 하여 접두어의 유무를 찾을 수 있다.

 

123, 1321, 1322 순으로 정렬된 전화번호가 있다고하자.

123에 대해 다음 문자열은 1321이다. 접두어가 존재하지 않는다. 그러면 123에 대해 1322와 비교할 필요가 없다.

사전식으로 정렬되어 있는데 다음 문자열인 1321에 존재하지 않는데 그 이후로 정렬된 문자열들은 안 봐도 비디오다.

 

왜냐하면 가장 비슷한 문자열들끼리 뭉쳐있기에 인접한 데이터가 가장 유사한 데이터이기 때문이다.

사전식으로 정렬하면 123, 1231, 1232 이런 식으로 접두어가 일치하는 것 또는 유사한 것끼리 뭉쳐있을 수밖에 없다.

그래서 현재 문자열과 다음 문자열을 비교하여 접두어가 존재하는지 알 수 있다. 

 

아래의 질문 답변글에서 이해를 했다.

https://school.programmers.co.kr/questions/39655

 

 

 

아래의 코드는 하나의 문자열을 모든 문자열과 비교하는 방법으로 시간초과가 난다.

#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    
    for(int i=0; i<phone_book.size(); i++)
    {
        for(int j=0; j<phone_book.size(); j++)
        {
            if(i==j||phone_book[i].length()>phone_book[j].length())
                continue;
            
            bool flag=false;
            for(int idx=0; idx<phone_book[i].length(); idx++)
            {
                if(phone_book[i][idx]!=phone_book[j][idx])
                    flag=true;
            }
            if(flag==false)
                return false;
            
        }
        
        
    }
    
    return answer;
}