#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
/*
 *[문제]
 * 접두어 전화번호가 존재하면 false 존재하지 않으면 true
 * 전화번호부가 담긴 phonebook 거기서 어떤 번호가 다른 번호의 접두어  - false
 * 접두어가 아님 true
 *
 *중복해서 들어있는 경우는 없다.
 *
 * [입력]
 * 전화번호부에 적힌 전화번호를 담은 배열 phone_book
 *
 * phone_book의 길이 1<= x <=10^7
 * 1<= 전화번호 길이 <=20
 *
 *
 * [출력]
 *  전화번호부가 담긴 phonebook에서 접두어를 찾음 -false
 *  아니면 true반환
 *
 * [IDEA]
 * 모든 경우의 수를 전부 다 돌아야한다. 이중 for문을 사용해서 모두 돌리도록 하자
 *
 * A가 접두어 B,C가 phonebook의 전화번호라고 하면 false가 나오려면 B나 C가
 * A의 길이 이상이어야하고 0,A.size까지의 값이 A와 동일해야한다.
 * 하나라도 찾으면 로직을 종료하고 false를 리턴한다.
 *
 *
 * [psudo code]
 *  answer = false //정답의 default값을 false로 지정
    phone_book을 sorting 수행
 *  이중 for문으로 데이터 검사
 *        - 접두어 A, 검사 단어 B
 *        - 검사단어 B의 0,size의 값이 A와 같나?
 *           true출력 로직 종료
 *
 * answer출력
 */
bool solution(vector<string> phone_book) {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    bool answer = true;
    
    //sort를 뺴면 8,9,19 번 TC가 에러가 났었음
    //sort(phone_book.begin(), phone_book.end());
    for(int i=0; i<phone_book.size(); i++){
        string A = phone_book[i];
        
        for(int k= i+1; k<phone_book.size(); k++){
            string B = phone_book[k];
            
            if(A == B.substr(0,A.size())){
                cout << false; return 0;
            }
        }
    }
    
    return answer;
}

해쉬를 이용한 방법

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
/*
 *[문제]
 * 접두어 전화번호가 존재하면 false 존재하지 않으면 true
 * 전화번호부가 담긴 phonebook 거기서 어떤 번호가 다른 번호의 접두어  - false
 * 접두어가 아님 true
 *
 *중복해서 들어있는 경우는 없다.
 *
 * [입력]
 * 전화번호부에 적힌 전화번호를 담은 배열 phone_book
 *
 * phone_book의 길이 1<= x <=10^7
 * 1<= 전화번호 길이 <=20
 *
 *
 * [출력]
 *  전화번호부가 담긴 phonebook에서 접두어를 찾음 -false
 *  아니면 true반환
 *
 * [IDEA] - 해쉬를 사용하는 경우
 * hashmap에 key : 문자열 int : 1 의 형태로 데이터를 저장한다.
   
   for문을 돌면서 string key값이 hash에 존재하는 경우를 찾는다.(접두사가 되는 경우)
   hash에 값이 존재하면서 hash의 key값과 동일하지 않으면(본인은 판별하지 않는다.)
   접두사가 존재하는 경우이다.
   
   참고로 왜 number += 문자열[i][j]를 해야하는 이유는 
   우선 phone_numbers 는 주어진 배열에 들어있는 값을 의미한다. 
   즉 number += 문자열[i][j]의 값은 접두사인가를 판별할 때 하용한다.(hash_map[numbers] ==1)
   
   그 다음 문자열[i] !=number 이여야 한다. 예를 들어 number = 12 문자열[i] = 1234라고 가정하자
   12는 입력받은 배열에 존재하는 값이다.
   
   hash_map(12)는 존재하는 값(접두사가 되는 값) 그리고 12 !=1234이다. 만약에 해당 조건을 넣지않으면
   자기 자신일때도 통과하는 결과가 나온다. 즉 배열안에 있는 값 12와 1234는 서로 다른 값임을 확인하기 위해서 넣어준다.

 *
 *
 * [psudo code]
 *  1. hash 선언
		 2. hash에 값 넣기 key : string(문자열 단어들) || value : 1
		 3. for문을 돌면서 문자열 접두사 하나하나 있는지 확인
		 
					 number = 문자열[i][j]
					 hash(number) || number != 문자열[i]여야 한다.
 */

/*
효율문제를 해결하기 위한 방안
1. phone_book을 사전순으로 정리한 후 인접한 인덱스끼리만 검사
위의 방법은 phone_book의 요소가 int가 아닌 string이라서 가능하다.O(n)에 끝낼 수 있다.

2. hash를 사용하는 방법

*/
bool solution(vector<string> phone_book) {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    bool answer = true;
    unordered_map<string ,int> hash_map;
    
    for(int i=0; i< phone_book.size(); i++){
        hash_map[phone_book[i]] =1; // key를 String으로 두었다.
        
    }
    
    for(int i=0; i< phone_book.size(); i++){
        string phone_number = "";
        for(int j=0; j< phone_book[i].size(); j++){
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])//phone_number != phone_book은 동일한 컨텐츠를 제외해야하므로 
                return false;
        }
    }
    
    return answer;
}

소요시간

18min(근데 첫 시도에 틀림 ㅋ)

해쉬란?

해쉬는 데이터를 좀 더 빨리 찾기 위해서 고안 되었음을 잊지 말자

c++에서 해쉬는 map을 통해서 구현한다.
map: binary search Tree 사용 O(NlogN)
unorderd_map : hash사용 O(1)

참고로 Set은 중복된 데이터를 허용하지 않는다.