프로그래머스 / 전화번호 목록

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

프로그래머스

 

처음엔 vector<string>을 sort하여 i와 i+1을 비교하는 방식으로 접근하려고 했는데

해시 문제인데 해시를 사용하지 않는 풀이방식이라 다시 생각해보았다

unordered_set으로 찾을 string 목록을 저장하고

각 단어마다 1부터 길이까지 substr하여 접두어 prefix가 있는지 find해서 해결했다

j < phone_book[i].size() 이므로 중복된 값을 찾는 일을 방지할 수 있다

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

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

    unordered_set<string> usPhone;

    for (int i = 0; i < phone_book.size(); ++i)
    {
        usPhone.insert(phone_book[i]);
    }

    for (int i = 0; i < phone_book.size(); ++i)
    {
        for (int j = 1; j < phone_book[i].size(); ++j)
        {
            string prefix = phone_book[i].substr(0, j);

            if (usPhone.find(prefix) != usPhone.end())
            {
                answer = false;
                return answer;
            }
        }
    }

    return answer;
}