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

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트라이

트라이를 통해 문제 해결을 할 수 있다.

소스 코드 : 

/*
    https://programmers.co.kr/learn/courses/30/lessons/42577
    트라이를 통해 문제를 해결한다.
*/
 
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
 
#define MAX_NODE 10
 
using namespace std;
 
struct Trie {
    Trie *next[MAX_NODE];
    bool isEnd;
    bool isVisited;
 
    Trie() {
        for (int i = 0; i < MAX_NODE; i++)
        {
            next[i] = nullptr;
            isEnd = isVisited = false;
        }
    }
    ~Trie() {
        for (int i = 0; i < MAX_NODE; i++)
            if (next[i])
                delete next[i];
    }
};
 
bool solution(vector<string> phone_book) {
    Trie *root = new Trie;
 
    for (int i = 0; i < phone_book.size(); i++) {
        Trie *cur = root;
        int len = phone_book[i].size();
        for (int j = 0; j < len; j++) {
            int nowCh = phone_book[i][j] - '0';
            if (cur->next[nowCh] == nullptr)
                cur->next[nowCh] = new Trie;
 
            // 현재 전화번호보다 짧거나 같은 번호가 여기서 isEnd라면
            // 그 번호는 현재 번호의 접두사이다.
            if (cur->isEnd)
                return false;
 
            // 이미 다른 번호가 여기를 지나갔고 현재 번호의 끝이면
            // 현재 번호는 다른 번호의 접두사이다.
            if (cur->next[nowCh]->isVisited && j == len - 1)
                return false;
 
            cur->next[nowCh]->isVisited = true;
 
            cur = cur->next[nowCh];
        }
        cur->isEnd = true;
    }
 
    return true;
}