[Programmers] 전화번호 목록 with Hash

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

이전에 푼 문제인데, 복습을 위해서 다시 정리해보았다.

 

서로의 번호를 매치하며 서로의 번호가 prefix인지를 확인한다.

하나는 prefix 번호, 다른 하나는 mateched 번호로 설정해서 이중 루프를 돌며 검색한다.

그런데 그렇게 되면 Hash가 아니라 일반 배열로 검색해도 되지 않을까? 라는 의문이 들 수 있다.

배열에서 matched 되는 번호를 매번 찾으면 시간 복잡도가 $O(N)$이다. 그러나 (충돌만 안 난다면...) 해시에서 찾으면 $O(1)$이다.

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    unordered_map<string, int> hash_map;
    // 번호 존재 여부 저장
    for(int i =0;i<phone_book.size();i++){
        hash_map[phone_book[i]] = 1;
    }
    
    // 다른 번호를 substring해서 해시에서 찾는다.
    for(int i = 0;i<phone_book.size();i++){
        for(int j = 0;j < phone_book[i].length();j++){
            if(hash_map.find(phone_book[i].substr(0, j)) != hash_map.end()){
                answer = false;
                break;
            }
        }
    }
    return answer;
}

여기서 주의할 점은 해시에서 key로 찾을 때 find 메소드를 쓰면 된다. 만약 없다면 해시의 end()가 리턴된다.