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

문제

풀이

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

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end()); 
    string str;
    //이중포문은 시간초과
    /*
    for(int i=0; i<phone_book.size()-1; i++){
        str = phone_book[i];
        for(int j=i+1; j<phone_book.size(); j++){ 
            if(str[0] != phone_book[j][0]) break;
            if(phone_book[j].find(str) == 0)
                return false;
        }
    }
    */
    
    for(int i=0; i<phone_book.size()-1; i++){
        if(phone_book[i+1].find(phone_book[i]) == 0)
                return false;
    }
    
    return answer;
}

1. phone_book벡터를 순서대로 정렬

2. 이중 포문을 돌며 접두사인지 확인

효율성이 0이 나온 풀이이다.

 

phone_book벡터를 순서대로 정렬하면, phone_book [index]가 phone_book [index+1]의 접두어인지만 확인하면 되기 때문에 코드를 수정해주었다.

 

1. phone_book 벡터 순서대로 정렬

2.  phone_book[index]가 phone_book[index+1]의 접두어인지만 확인

 

---

 

 

 

다른 사람 풀이 1

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

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

    sort(phoneBook.begin(), phoneBook.end());

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}

접두어인지 확인할 때 나는 find함수를 활용했으나, 위의 코드는 substr을 활용했다.

 

 

 

다른 사람 풀이 2

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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;
}

문제 요구대로 해시를 활용한 풀이이다.