[C++, Hash] 프로그래머스 전화번호 목록 문제 풀이

문제 링크

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

 

풀이

코딩테스트에서 해시관련 문제가 좀 약한 느낌이 들어서 해시관련 문제를 풀어보았다.

풀면서 사람들의 여러 코드를 참고하였는데 정작 해시를 이용한 문제풀이는 많이 없었다.

 

아래는 내가 처음 떠오른 아이디어로 풀이한 코드이다.

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

using namespace std;

bool solution(vector<string> phone_book) {
    for (string cand : phone_book) {
        
        int cand_size = cand.size();
        
        for (string phone_num : phone_book) {
            if (cand_size > phone_num.size() || cand==phone_num) continue;
            string sub_num = phone_num.substr(0,cand_size);
            if (cand.compare(sub_num) == 0) {
                return false;
            }
        }
    }
    
    return true;
}

단순히 하나씩 비교해서 접두어인 번호를 찾는 방식이다.

시간복잡도가 O(N^2)라서 효율성에서 틀릴 줄 알았지만 맞아서 의외였다..

그냥 선형으로 풀어도 풀린다니..

 

이외에도 정렬을 이용한 풀이법이라던지 여러 풀이가 많았지만

해시개념을 써서 푼 풀이를 보고 다시 풀이를 작성해 보았다.

Trie를 사용한 풀이법이다.

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

using namespace std;
bool answer;
class Trie
{
public:
    Trie* next[10];
    bool is_next;
    bool is_finish;

    Trie()
    {
        is_next = false;
        is_finish = false;
        memset( next, 0, sizeof(next));
    }
    
    ~Trie(){
        for(int i=0;i<10;i++){
            if(next[i])
                delete next[i];
        }
    }

    void insert(string str)
    {
        if(str.size() == 0)
        {
            is_finish = true;
            if (is_finish == is_next) // 1195524421 119 순으로 나오는 경우
                answer = false;
            return;
        }
        int next_num = str[0] - '0';

        if(next[next_num] == 0)
        {
            next[next_num] = new Trie;
            is_next = true;
            if(is_finish == true){ // 119 1195524421 순으로 나오는 경우
                answer = false;
                return;
            }
        }

        next[next_num]->insert(str.substr(1,str.size()-1)); 
    }
};

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

    Trie *root = new Trie;
    
    for (string phone_num : phone_book)
    {
        root->insert(phone_num);
        if(!answer) break;
    }

    return answer;
}

위의 비록 구현이 쉬운편은 아니지만 출재자의 의도에 맞게 푼 것 같다.

질문이 있다면 답글로 부탁드린다.