[ 백준 5052 ] 전화번호 목록 (C++)

백준의 전화번호 목록(5052) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 전화번호를 입력할 때, 일관성이 있는지 없는지 판단해야 하는 문제이다.

먼저, 본인은 전화번호를 "문자열"이라 생각하고 이 전화번호를 자료구조 트라이(TRIE)로 관리해주었다.

글을 읽기 전에, 트라이에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 자료구조 트라이(TRIE) 알아보기 ]

위의 글에서 설명한것과 같이, 입력되는 전화번호들을 먼저 트라이로 관리하기 위해서 트라이에 입력해주었다.

트라이에서 관리하는 멤버변수로는 해당 문자가 마지막 문자임을 알 수 있게 표시해주는 'Finish' 변수와, 노드를 생성

하기 위한 TRIE *형 배열, 이 2개의 멤버변수를 만들어서 관리해주었다.

트라이에 등록한 이후에, 순차적으로 전화번호를 찾는데, 아직 전화번호가 끝이 나질 않았는데, 마지막 문자라고 표시되어

있는 경우에는 그대로 "NO"를 출력해주었다.

예를 들어서 [ 911234 , 911 ] 이 입력되어 있을 때, 911234를 트라이에서 하나씩 찾아가는 경우를 보면

"911" 이라는 번호 때문에 9 → 1 → 1 까지 갔을 때, Finish변수에 표시가 되어 있을 것이다. 이는, 911234에 전화를 걸지

못한다는 것이므로 일관성이 없다고 판단할 수 있다.

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
#define LEN_MAX 11
#define N_MAX 10010
#define NODE_MAX N_MAX * LEN_MAX
using namespace std;
 
struct TRIE
{
    bool Finish;
    TRIE *Node[LEN_MAX];
    
    void Insert(char *Str);
    bool Call(char *Str);
};
 
int N, N_Idx;
char Phone[N_MAX][LEN_MAX];
string Answer;
TRIE *Root, Nodepool[NODE_MAX];
 
TRIE *Nodeset()
{
    TRIE *NewNode = &Nodepool[N_Idx++];
    NewNode->Finish = false;
    for (int i = 0; i < LEN_MAX; i++) NewNode->Node[i] = NULL;
    
    return NewNode;
}
 
void TRIE::Insert(char *Str)
{
    if (*Str == NULL)
    {
        Finish = true;
        return;
    }
 
    int Cur = *Str - '0';
    if (Node[Cur] == NULL) Node[Cur] = Nodeset();
    Node[Cur]->Insert(Str + 1);
}
 
bool TRIE::Call(char *Str)
{
    if (*Str == NULL) return true;
    if (Finish == true) return false;
 
    int Cur = *Str - '0';
    return Node[Cur]->Call(Str + 1);
}
 
void Initialize()
{
    N_Idx = 0;
    Root = Nodeset();
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Phone[i];
}
 
void Solution()
{
    for (int i = 0; i < N; i++) Root->Insert(Phone[i]);
    bool Flag = true;
    for (int i = 0; i < N; i++)
    {
        if (Flag == true) Flag = Root->Call(Phone[i]);
        if (Flag == false) break;
    }
 
    if (Flag == true) Answer = "YES";
    else Answer = "NO";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}