알고리즘(C++) / 프로그래머스 level 2 : 전화번호 목록

level 2 : 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577?language=cpp 

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

 

코드

//프로그래머스 전화번호 목록
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

bool cmp(const string& a, const string& b) {
    return a.size() < b.size();
}

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

    sort(phone_book.begin(), phone_book.end(), cmp); //정렬

    map <string, int> m;

    for (int i = 0; i < phone_book.size(); i++) {
        for (int j = phone_book[0].size(); j <= phone_book[i].size(); j++) {
            if (m[phone_book[i].substr(0, j)] == 1)
                return false;
        }
        m[phone_book[i]]++; //해쉬
    }
    return true;
}

int main() {
    vector<string> phone_book = { "119", "97674223", "1195524421" };
    cout << solution(phone_book) << "\n";
    return 0;
}

 

설명

• phone_book을 size가 큰 순으로 정렬한다. 
• 전화번호를 잘라 map에 존재하는지 확인한다.
• 자른 string이 길이가 map에 존재한다면 return false를 출력한다.
• 접두어가 아닌 경우 true를 출력한다. 

 

고찰

걸린시간 : 40분

해시를 사용하여 문제를 해결할 수 있었다. 해시를 사용하여 문제를 해결해야지만 효율성 테스트를 통과할 수 있다.