[코딩테스트 연습] hash-전화번호목록

hash를 사용한 코드

---

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> hash_map;
    int phoneLen = phone_book.size();
    
    for(const string& phone_key : phone_book){
        hash_map[phone_key] = 1;
    }
    
    for(const string& phone : phone_book){
        string phone_number = ""; 
        
        for(const char& phone_one : phone){
            phone_number += phone_one;
            
            if(hash_map[phone_number] && phone_number != phone)
                return false;
        }
    }
    
    return true;
}

풀이 : 전화번호목록의 전화번호를 하나하나씩 조합해보면서 접두사가 있는지 찾는다

 

중요한 구문

if(hash_map[phone_number] && phone_number != phone) 

hash_map[phone_number] : phone_number이란 번호가 있는지 알려준다

phone_number != phone : 자기자신과 같은 번호는 없으므로 번호가 완성될 때 끝낸다

 

여기서 중점은 본인이 접두사인지 확인하는 것이 아니라 본인의 접두사를 찾는 것이다

 

다른 방법을 사용한 코드

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool solution(vector<string> phoneBook) {
    bool answer = true;

    sort(phoneBook.begin(), phoneBook.end());

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}

풀이 : sort를 사용하여 전화번호목록를 정렬하면 사전순으로 정렬이 되는데 여기서 인접번호만 조사하면 접두사를 알아낼 수 있다

 

중요한 구문

for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
{
    if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
    {
        answer = false;
        break;
    }
}

for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ ) : 현재(조사되고 있는) 번호와 다음 번호를 조사하므로 phoneBook.size()-1만큼 조회한다

phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size())  : substr를 사용해서 다음 번호의 앞부분을 현재 번호의 크기만큼 잘라낸다 잘려낸 번호는 현재 번호와 비교해서 현재 번호가 접두사로 사용될 수 있는지 검사한다 

 

여기서 중점은 현재 번호가 접두사로 사용될 수 있는지 알아보는 것이다