<Programmers> Hash_전화번호 목록 c++

먼저 hash로 구하는 방법 말고는
phone_book을 sort()하고, 인접한 두 string을 비교하면 된다.

예를 들면
["119", "97674223", "1195524421"] 이 있을 때 이것을 정렬하면
["119", "1195524421", "97674223"] 순으로 되고
"119"와 "1195524421", "1195524421"과 "97674223"을 비교한다.
(만약 이게 string형이 아니고 정수형이었다면 string형으로 변환 후 비교해야 한다)

두 string 을 비교할 때, 같은 값을 찾는 게 아니고 접두어인지 확인하는 것이기 때문에 i번 째 문자와 i+1번 째 문자의 i번 째 문자의 길이만큼 비교한다.
phone_book[i]==phone_book[i+1].substr(0, phone_book[i].size())

1. sort를 이용한 방법

#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 answer=false;
    }    
    return answer;
}

2. hash를 이용한 방법

1) unordered_map을 정의한 후, map의 key값에 phone_book의 값을 넣고 value에 1을 넣어준다.

unordered_map<string, int> map;
for (string number: phone_book)
        map[number]=1;

2) phone_book 에 저장된 번호를 한 글자씩 받아오면서 map에 있는 key와 비교한다.

e.g. map[119]=1 인 상태이고
phone_book[0]="119" 에서 "1", "19",
phone_book[1]="97674223" 에서 "9", "97", "976", ... "9767422"
phone_book[2]="1195524421"에서 "1", "11", "119" ... "119552442"
를 차례로 string phone_number에 넣어보며 map[phone_number]=1인지 찾는다
(여기서 찾는 것은 접두사 이기 때문에 문자를 끝까지 넣지 않고 하나를 뺀 문자까지만 넣어 비교한다)

for (int j=0; j<phone_book[i].size()-1; j++) {
            phone_number+=phone_book[i][j]; 
            if (map[phone_number]) return answer=false;
        }

소스코드

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
   
    unordered_map<string, int> map;

   for (string number: phone_book)
        map[number]=1;
    for (int i=0; i<phone_book.size(); i++) {
        string phone_number="";
       
        for (int j=0; j<phone_book[i].size()-1; j++) {
            phone_number+=phone_book[i][j]; 
            if (map[phone_number]) return answer=false;
        }
    }    
    return answer;
}