전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

---

문제 풀이

전화번호의 다른 번호의 접두어인 경우가 있는지 확인하려 한다.

들어간 전화번호 중, 중복된 전화번호가 존재하는지 확인하려고 하는 문제이다.

 

탐색알고리즘에서 가장 효율적 인것은 헤시키 값 이고, 그 다음이 트리 구조이다.

 

트리구조로 탐색하도 무방하고, 해시를 사용해도 무방하다.

 

그냥 모든 키값의 string값을 순환하면서 0~현재 문자까지의 모든 문자를 순환하면서 해시값으로 데이터를 확인하고, 해당 데이터에 +1을 해준 뒤에, 들어온 모든 문자열을 확인하면서 1 이상인 값이 있다면, false 아니면 true를 반환하면 된다.

매우 쉬운 문제.

---

첫 시도

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

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> answer_map;
    for(const string& phone_number : phone_book)
    {
        for(int i = 0; i < phone_number.size(); i++)
        {
            string input = phone_number.substr(0, i);
            answer_map[input] += 1;
        }
    }
    for(const string& phone_number : phone_book)
        if(answer_map[phone_number] >= 1)
            return false;
    
    return true;
}

성공

 

위 설명과 같이. 그냥 unordered_map을 생성하고, string -> string.size() 로 순환하면서 모든 문자열에 대해 중복되는 경우가 생기는 것을 헤시키로 중복처리하고 데이터를 기입. 그리고 1을 더해준다음.

 

입력받은 모든 숫자열에 대해 1 이상인 경우가 존재하면 false로 처리. 아니라면 true로 처리한다.