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

문제 설명

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

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

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

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

---

풀이

phone_book의 번호를 오름차순으로 정렬한 뒤, 정렬된 벡터 내에서 바로 뒤의 원소와만 비교하여 시간을 줄여보았다. 풀이 중에 이 코드가 효율성을 통과할 수 있는지가 애매했다. 일단 떠오르는 방법으로 코드를 작성했지만, 1) string vector를 sort하는 과정 자체의 시간복잡도가 너무 크지는 않을지 2) 이 문제의 분류는 hash인데, 이렇게 풀 수 있는 문제인지

의 두 가지 측면에서 자신할 수 없었다. 하지만 다시 생각해보니 string의 최대 길이가 20이므로, 20*20 = 400이라는 상수를 정렬하는 시간복잡도 O(nlogn)에 곱하여도 그대로 O(nlogn)이 유지되었다. 막연하게 ‘좀 오래걸릴 것 같은데..?’라는 생각에서 벗어나 한 번만 더 생각하면 바로 깨달을 수 있는 부분이었던 것 같아 아쉽다.

코드

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

다른 코드

대부분 직관적으로 정렬하여 푼 경우가 많았는데, 다른 사람들의 코드 중 해시로 접근한 코드를 볼 수 있었다. 시간 복잡도에 차이가 없다고 판단되는데, 굳이 이 문제를 해시로 분류한 이유를 잘 모르겠다.

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

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}