[프로그래머스]해시 : 전화번호 목록 (level 2) (c++)

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

프로그래머스

 

방법 1: 정렬 후 앞/뒤 문자열을 비교

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {

    int len = phone_book.size();

    // 사전순 오름차순 정렬
    sort(phone_book.begin(), phone_book.end());

    // 앞 번호 전체와 뒷번호 일부분 비교
    for (int i = 0; i < len - 1; ++i)
    {
        if (phone_book[i + 1].compare(0, phone_book[i].size(), phone_book[i]) == 0)
        {
            return false;
        }
    }

    return true;
}

 

방법 2: 해시맵에 저장 후, 등장 빈도수 카운트

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

using namespace std;

bool solution(vector<string> phone_book) {

    // key : "전화번호의 일부" , value : 빈도수
    unordered_map<string, int> split_book;

    // 모든 전화번호의 일부를 해시맵에 저장하고 빈도수 카운트
    int len = phone_book.size();
    for (int i = 0; i < len; ++i)
    {
        string number = "";
        for (int j = 0; j < phone_book[i].size(); ++j)
        {
            number += phone_book[i][j];
            ++split_book[number];
        }
    }

    // 전화번호의 빈도수가 1 초과이면 false리턴
    for (int i = 0; i < len; ++i)
    {
        if (split_book[phone_book[i]] > 1)
        {
            return false;
        }
    }

    return true;
}

 

 

문제가 해시 분류이기 때문에 2번으로도 풀어봤다.

당연히 효율은 1이 훨씬 낫다 ㅋㅋ

 

string compare 참고 사이트: 

https://www.geeksforgeeks.org/stdstringcompare-in-c/

 

unordered_map 참고 사이트:

http://www.cplusplus.com/reference/unordered_map/unordered_map/begin/