[프로그래머스] 전화번호목록

문제 요약

1. 최대 10^6 개의 전화번호 문자열(최대 20)이 담긴 벡터가 주어집니다.
2. 어떤 하나의 전화번호라도 다른 전화번호를 접두어로 가지는지를 리턴하세요.

아이디어

해시 문제를 풀어보고 싶어 고른 문제이니만큼 일부러 해시로 풀었다.
인터넷 찾아보니 O((10^6)^2 * 20)으로 모든 문자열에 대해 전체 전화번호부를 훑어도 통과 할 수 있었다.

해시는 그냥 가장 간단하게 각자리의 숫자를 더해서 인덱스를 구성하고
close addressing으로 각 버켓에 어펜드해주었다.

삽질

8, 9번 테케가 틀렸었는데
내가 for문 하나에서 각 문자열에 대해 1. 테이블에서 접두사들이 일치하는지 찾고 2. 자신을 테이블에 해싱해서 넣어주고
이런 식으로 해주어서 틀렸다.
예를 들면 첫번째 문자열의 경우 자신이 다른 문자열을 접두어를 가질 수 있는지 검사하지 않았던 것이다.

질문란을 보고 전체 문자열을 미리 테이블에 넣어주는 식으로 바꿔주었다.

내 코드

#include <string>
#include <vector>

using namespace std;

vector<int> tab[200];//180까지 나올 수 있긴함

int hash_(string s){
    int res = 0;
    for(int i = 0;i<s.size();i++){
        res+=s[i]-'0';
    }
    res = res%200;
    return res;
}

bool solution(vector<string> phone_book) {
    bool answer = true;
    //인터넷 검색 결과로는 나머지에 대한 문자열 앞머리 비교도 된다 하는데
    //일부러 해싱 써서 시간 좀 줄여보자..
    bool redun = false;
    for(int i = 0;i<phone_book.size();i++){//미리 넣어둠
        int res = hash_(phone_book[i]);
        tab[res].push_back(i);
    }

    for(int i = 0;i<phone_book.size();i++){
        string cur = phone_book[i];
        for(int j = 1;j<=cur.size();j++){
            int h =hash_(cur.substr(0,j));
            for(int k = 0;k<tab[h].size();k++){
                int idx = tab[h][k];
                if(idx== i){//나랑의 비교는 ㄴㄴ 
                    continue;
                }
                if(phone_book[idx]== cur.substr(0, phone_book[idx].size())){
                    redun = true;
                    break;
                }
            }
            if(redun){
                break;
            }
        }
        if(redun){
            break;
        }
    }
    answer= !redun;
    return answer;
}

배운점

다른 분 코드를 보니 unordered_map을 사용하셨더라.
나는 그냥 map 밖에 몰라서 map이면 넣고 찾고 할 때 O(1)이 안되니까 생각도 안 했는데 unordered_map의 존재를 알게 되었다.

unordered_map<string, int> hash_map;
hash_map[phone_book[i]] = 1;
if(hash_map[phone_number]){

}