[C++/PGS] Lv.2 : 전화번호 목록 (해시)

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

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

---

 

쉬운 문제이지만 효율성 테스트에서 점수가 계속 깎였던 문제!!

질문들 중 어떤 분의 친절한 풀이에서 그 해답을 얻을 수 있었다.

 

thanks to

 

정렬을 한 후 문제를 풀면,

"119"와 "1190"을 비교하면 접두어이므로 다음 값도 비교하면 되는데

"119"와 그 다음 값인 "1291"을 비교하면 접두어가 아니다. 그러면 "1291"의 다음 값들은 당연히 "119"를 접두어로 가지지 않을 것임.

왜냐면?

sort 정렬 시 문자열이므로 숫자 기준 정렬과는 다르게 정렬되기 때문이다!! (잘 생각해볼 것)

문자열의 내용이 숫자인 경우, 문자열 정렬 시  "11" > "112" > "12" > "123" ... 이다

 

그래서 그냥 비교하다가 접두어가 아닌 경우에는 반복문에 break;를 걸어주면 효율성 테스트 통과!!

 

 

나의 풀이

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

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for(int i=0; i<phone_book.size()-1;++i){
        string a = phone_book[i];
        for(int j=i+1;j<phone_book.size();++j){
            string b = phone_book[j].substr(0,a.size());
            if(a==b) return false;
            else break;
        }
    }
    return true;
}