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

삼성기출만 풀다가 시뮬레이션만 연습하나 싶어서 프로그래머스 코딩테스트 고득점 Kit을 풀어보기로 했다

해시부터 차례로 풀어보려했는데

이 문제는 보자마자 해시말고 Trie로 푸는 방법이 생각나서 그냥 트라이로 풀어보았다

구현도 쉽고 효율성도 좋아서 알고리즘 풀때 쓰기 좋아하는 자료구조

 

#include <string>
#include <vector>
 
using namespace std;
 
class Trie{
   public:
      Trie* child[10];
      bool isTerminal;
      Trie(){
         for(int i = 0 ; i < 10 ; i++) child[i] = NULL;
         isTerminal = false;
      }
      bool Insert(string str){
         Trie* ptr = this;
         int len = str.length();
         for(int i = 0 ;i < len ; i++){
            if(ptr->child[str[i]-'0']==NULL){
               ptr->child[str[i]-'0'] = new Trie();
            }else{
               if(i==len-1) return false;
               if(ptr->child[str[i]-'0']->isTerminal){
                  return false;
               }
            }
            ptr = ptr->child[str[i]-'0'];
         }
         ptr->isTerminal = true;
         return true;
      }
};
 
bool solution(vector<string> phone_book) {
    answer = true;
    Trie* root = new Trie();
    for(auto it = phone_book.begin() ; it!=phone_book.end() ; it++){
        bool inserted = root->Insert(*it);
        if(!inserted) return false;
    }
    return true;
}

 

차례로 전화번호들을 저장하면서 

두가지를 추가로 확인해주었다

 

먼저 체크한건 지금 삽입하고자 하는 전화번호의 마지막 숫자가 다른 번호의 경로를 그대로 따라가는지이다

예를들면 11223은 112233의 접두어이기 때문에 첫번째 번호의 마지막 위치인 3이 다른 전화번호에 속하므로 false를 보내주어야한다

if(i==len-1) return false;

 

이것을 통해 마지막 위치가 이미 생성되어 있다면 경로가 존재하는 것이라고 판단하여 false를 return 했다

 

다음으로 체크한건 전화번호 경로를 만들어가는 중 이미 그 칸이 다른 전화번호의 마지막 위치라고 체크가 된 경우이다

11223을 먼저 넣고 112233을 넣으면 두번째 번호의 마지막 3을 넣기 전에 이미 첫번째 번호때문에 isTerminal == true인 경우를 만나게 된다

if(ptr->child[str[i]-'0']->isTerminal) return false;

이렇게 체크해서 false를 return 해주었다

 

중간에 삽입에 실패하면 solution을 종료해주었고

모든 번호를 삽입 가능하다면 true return으로 마무리!