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

효율성 3, 4실패 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    for(int i = 0; i < phone_book.size(); i++)  //지정된 전화번호
    {
        int counts = 0;
        for(int j = 0; j < phone_book.size(); j++)  //비교할 전화번호
        {
            if(i == j) continue;    //비교할 것이 같으면 패스
                
            for(int k = 0; k < phone_book[i].size(); k++)   //지정된 전화번호길이만큼 비교
            {
                if(phone_book[i][k] != phone_book[j][k])    //비교하다가 틀리면 바로 패스
                {
                    counts = 0;
                    break;
                }
                
                if(phone_book[i][k] == phone_book[j][k])
                    counts++;
            }
            
            if(counts == phone_book[i].size())  //길이가 같다면 접두어가 있음
                break;
            else 
                counts = 0;
        }
        
        if(counts > 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() - 1; i++) 
    {
        if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size()))
            return false;
    }
    
    return answer;
}

 

풀이

1. sort로 오름차순으로 접두어가 비슷하도록 정렬한다.
2. 현재 전화번호의 접두어와 다음 전화번호의 접두어가 같은지를 확인한다.
3. 있으면 false로 종료