[알고리즘C++]전화번호 목록

오늘의 문제

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

전화번호 목록

나의 풀이

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    set<int> size;
    set<string> num_set;
    for(int i=0;i<phone_book.size();i++){
        if(num_set.insert(phone_book[i]).second == false)
            return false;
        size.insert(phone_book[i].size());
    }
    for(int i=0;i<phone_book.size();i++){
        set<int> ::iterator Iter_Pos = size.begin();     
        for(;Iter_Pos != size.end();Iter_Pos++){ // 들어있는 사이즈 만큼
            string comp = phone_book[i].substr(0, *Iter_Pos);
            if(num_set.find(comp) != num_set.end()){ // 찾음
                if(*num_set.find(comp) != phone_book[i])
                    return false;
            } 
        }
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool solution(vector<string> phoneBook) {
    bool answer = true;

    sort(phoneBook.begin(), phoneBook.end());

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}

배울 점

• 우와 정렬로 끝난다!!
• 사전적인 정렬을 하면 앞이 일치하는 것을 잡아낼 수 있다..
  와.. 생각도 못함
• string나오면 일단 정렬을 생각해보자