[C++] 전화번호 목록

[문제]

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

---

[문제 풀이]

hash를 써서 풀수도 있지만 보다 쉬운 풀이가 있었다.

우선 sort를 써서 전화번호를 정렬해주자.

그리고 해당 전화번호의 바로 뒤의 인덱스의 접두사가 자신이라면 false를 아니라면 true를 return 해주자.

이렇게 했을때 풀리는 이유는 만일 119, 1198, 118이 있다면 정렬을 했을 때 해당 값들이 int가 아니라 string이기 때문에 118, 119, 1198순으로 정렬이 될 것이고 바로 뒤의 숫자의 접두사와 자기가 최대한 일치되는 숫자들로 정렬이 될 것이기 때문이다.

---

[코드]

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(),phone_book.end()); // 사전순으로 정렬
    
    for(int i = 0;i<phone_book.size() - 1;i++){
        //만일 뒤의 코드가 앞의 코드의 접두사라면 false return
        if(phone_book[i] == phone_book[i+1].substr(0,phone_book[i].size())){
            return false;
        }
    }
    
    return answer;
}