[Programmers] 전화번호부

문제

문제 해결 전략

우선 python으로 문제를 해결한다면 훨씬 간편해질 것 같다는 생각은 python 유저라면 누구나 생각했을 것 같다. 하지만 나는 c++로 지금 문제를 해결하려고 하고 있기 때문에 좀 고민을 해봤다. 가장 짧을 문자열을 앞에 오게 정렬을 한 후에 정련된 값에 for loop을 한 번 돌려서 나를 제외한 뒤에 문자열과 내 문자열 길이 만큼 겹치는 것이 있으면 loop을 빠져나오게 한 번 짜보려고 한다.

코드1

실패한 코드...

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

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();i++){
        for(int j = i+1;j < phone_book.size();j++){
            if(i == j) break;
            else if(phone_book[i].find(phone_book[j]) != 0) return false;
        }
    }
    return answer;
}

우선 이렇게 짰을 때는 문제가 해결 되지 않았다.

코드2

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

using namespace std;

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

결국 다른 풀이 안보고 스스로 해결!!! 뿌듯하다. 우선 코드를 처음에 빠르게 짰을때는 우선 정렬부터 하고보자 하고 들어갔는데 생각을 해보니 사전순으로 정렬을 해준 후에 인접한 배열만 확인 하면 된다는 사실 을 깨우쳐서 바로 그대로 코드를 짜보았다. 문제를 풀면서 다른 사람들 코드를 확인해보니 나름 나도 나름 간결하게 짠 것 같다. 다른 사람 코드중에 내가 생각하지 못한 함수가 나와 한 번 정리해 보려고 한다.

substr

if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size))

대충 코드를 살펴보니 substr함수는 앞에 벡터 문자열의 부분 문자열로 크기가 phone_book[i] 사이즈의 부분 문자열과 phone_book[i]가 일치하는지 확인하는 방식으로 해결한 것 같다.