[프로그래머스 2 / c++] 전화번호 목록 - 해시

해쉬를 이용해서 풀라는 문제 같은데, 정렬을 사용 후 앞뒤만 비교하는 것이 더 효율적인 함정 문제이다

하지만 배우는 입장에서는 두 경우 모두 배울점이 많았다

정렬은 sort 후 다음 요소에 이전 요소를 find하여 0인지로 접두어를 찾는 아이디어!(없으면 ::npos가 나올 것이다)

해시는 아직 사용 경험도 부족한 만큼 원리이해와 key값이 없을때 key가 map에 추가되고 0의 value를 갖는점,

substr 을 루프에 활용하는 아이디어 등을 배울 수 있었다 

#include <bits/stdc++.h>

using namespace std;

bool solution(vector<string> phone_book) {
    
//     1. 정렬 후, 뒤의 숫자에서 앞의 숫자 find 하기
    
//     오름차순 정렬 후, 뒤의 숫자가 앞의 숫자를 포함하는지 확인. find로 뒤 숫자를 탐색
//     만약 find결과 0이 나오면 맨 앞에 위치해있다는 것으로 접두어 있으므로 false 리턴
//     루프 끝까지 돌아도 탐색이 0이 나오는 경우가 없다면 접두사 없으니 true 리턴
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){ // 앞뒤 인덱스를 같이 봐야하니 -1번 이동
        if(phone_book[i+1].find(phone_book[i])==0)
            return false;
    }
    return true;
}
//
// -----------------------위는 정렬, 아래는 해쉬 맵 이용------------------------

bool solution(vector<string> phone_book) {
    
    // 2. 해시 맵을 이용해서 가능한 접두어들이 맵에 존재하는지 확인하기
    
    // 해시맵을 만들고 초기화한다. 비교하여 중복이나 비는것이 아니니 value는 존재여부 확인을 위해
    // 1 이상의 수로 초기화 해준다
    // phone_book 의 요소마다 다음을 실행한다
    // 요소 앞에서부터 1부터 요소길이-1 까지 각각 자른 길이의 경우의 수들을 해시맵에
    // 접두어와 같은 key값이 존재하는지 확인한다
    // 6328을 자를시 접두어 중 하나인 63이 key에 같은 값이 있다면
    // 그 63이 다른 값의 접두어가 되는 것이다. 이를 루프를 돌며 모두 확인. 있으면 false 리턴한다
    // 모두 돌았는데도 false가 없었다면 true이다
    
    unordered_map<string, int> map;
    for(int i=0; i<phone_book.size(); i++){
        map[phone_book[i]]=1;
    }
    for(int i=0; i<phone_book.size(); i++){
        for(int j=1; j<phone_book[i].size(); j++){
            string phone_num="";
            phone_num=phone_book[i].substr(0, j); // 접두어이므로 앞에서부터 추출한다
            if(map[phone_num]) // 없는 key이면 value는 디폴트 0을 갖고 map에 추가된다
                return false;                
        }
    }
    return true; // 모두 돌아도 없으면 true를 반환하자
}