[Algorithm] 프로그래머스 전화번호 목록 - C++, unordered_map

코딩테스트 연습 - 전화번호 목록

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> numbers;

    for(int i = 0; i < phone_book.size(); i++){
        numbers[phone_book[i]] = 1;
    }

    for(int i = 0; i < phone_book.size(); i++){
        string prefix = "";
        for(int j = 0; j < phone_book[i].size(); j++){
            prefix += phone_book[i][j];
            if(numbers[prefix] && prefix != phone_book[i])
                return false;
        }
    }

    return true;
}

---

 map에 대한 숙련도를 높이고자 찾아본 문제로 unordered_map을 활용해 풀이한 문제입니다. unordered_map의 경우 해시를 이용해 O(1) 시간복잡도를 가지는 자료구조로 map과 다르게 정렬이 없어 이런 문제를 푸는데 도움이 되었습니다. 

 

 주어진 데이터의 전화번호를 전부 넣어준 뒤 차례차례 아래 for문에서 탐색을 하는 것입니다. 탐색 방법은 폰 번호를 1개 가져온 뒤 이 번호를 하나씩 끊어서 이걸 사용하고 있는 번호가 있다면 접두사가 있다는 뜻으로 처리를 했습니다.