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

문제

 

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

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

문제풀이

 

한 번호가 다른 번호의 맨 앞에 있는 경우가 있는지를 확인하는 문제이다.

전화번호 목록을 크기 순으로 정렬하고, unordered_set을 이용하였다.

 

전화번호를 맨 앞부터 한 자리씩 str에 더한다.

전화번호가 저장된 unordered_set에서 str이 있는지 확인하고 있다면 바로 false를 return 한다.

끝까지 가도 없으면 현재 전화번호를 unordered_set에 저장한다.

 

코드

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

bool cmp(string& s1, string& s2) {
    return s1.size() < s2.size();
}

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end(), cmp);
    unordered_set<string>num;
    string str("");
    for (int idx = 0; idx < phone_book.size(); ++idx) {
        str.clear();
        for (int idx2 = 0; idx2 < phone_book[idx].size(); ++idx2) {
            str += phone_book[idx][idx2];
            if (num.find(str) != num.end()) return false;            
        }
        num.insert(str);
    }

    return true;
}