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

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

프로그래머스

풀이

풀이 1. 사전순으로 정렬 후 접두어 찾기

사전순으로 정렬하면 후 단어에서 전 단어가 접두어로 존재하는지만 검사하면 된다.

풀이 2. unordered_map을 사용해 접두어 찾기

현재 단어에서 검사 길이를 늘려가면서 임의의 단어를 만들고, 해쉬 맵에서 검색해서 존재한다면 false 를 리턴하면 된다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for (int i=0; i<phone_book.size()-1; i++){
        string ref=phone_book[i];
        if (phone_book[i+1].find(ref) != string::npos
           && phone_book[i+1].find(ref) == 0){
            return false;
        }
    }
    
    return true;
    
//     unordered_map<string, int> hash_map;
    
//     for(int i = 0; i < phone_book.size(); i++)
//         hash_map[phone_book[i]] = 1;

//     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])
//                 return false;
//         }
//     }
//     return true;
    
}