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

문제링크

https://www.acmicpc.net/problem/5052

풀이방법

해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다.

아래 코드에 대한 상세 설명은 다음과 같고 추가적으로 주석에 설명을 덧붙였다.

코드 설명

1. c2i 함수: 문자를 정수로 변환해주는 함수입니다. '0'부터 '9' 사이의 문자에 대해 해당 문자의 정수값을 반환합니다.
2. insert 함수: 주어진 전화번호를 트라이에 추가하고 중복 여부를 검사하는 함수입니다. 아래는 함수의 주요 동작을 설명한 것입니다.
   • cur 변수를 루트 노드로 초기화합니다.
   • 문자열 s의 각 문자 c에 대해 다음을 반복합니다.
     • cur 노드에서 문자 c에 해당하는 다음 노드가 없다면(nxt[cur][c2i(c)] == -1), 새로운 노드를 생성하고 그 노드의 인덱스를 nxt[cur][c2i(c)]에 할당합니다. 이렇게 함으로써 새로운 문자를 추가합니다.
     • cur을 nxt[cur][c2i(c)]로 업데이트하여 다음 문자로 이동합니다.
     • 만약 현재 노드가 이미 검사된 번호의 끝을 나타내는 노드라면(chk[cur] == true), 중복된 번호가 발견된 것이므로 false를 반환하고 함수를 종료합니다. 즉, 중복된 문자열이므로 일관성이 없습니다.
   • 문자열의 모든 문자를 처리한 후, 만약 cur이 새로 생성된 노드가 아니라면 이미 생성된 번호를 사용한 것이므로 중복을 의미합니다. 즉, 중복된 문자열이라는 의미로 일관성이 없습니다.
   • chk[cur]을 true로 설정하여 현재 번호를 끝을 나타내는 노드로 표시합니다.
   • 모든 과정이 끝나면 true를 반환하여 현재 번호가 중복이 아니라는 것을 알려줍니다. 즉, 중복되지 않았으므로 일관성이 있습니다.
3. main 함수: 입력을 받고 각 테스트 케이스마다 insert 함수를 호출하여 번호를 추가하고 중복 여부를 확인합니다. 결과에 따라 "YES" 또는 "NO"를 출력합니다.

이 코드는 효율적인 트라이 자료구조를 활용하여 주어진 전화번호들 중에서 중복된 번호가 있는지를 효과적으로 판별하는 프로그램입니다.

https://www.youtube.com/watch?v=ZmLe4tc5XRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=32

코드

#include <bits/stdc++.h>
using namespace std;

const int MX = 10000 * 10 + 5;
const int ROOT = 1;

int unused = ROOT+1;
int nxt[MX][10];
bool chk[MX];

int t, n;


int c2i(char c)
{
    return c - '0'; // 'A' == 0
}

bool insert(string& s)
{
    int cur = ROOT;
    for (auto c : s)
    {
        if (nxt[cur][c2i(c)] == -1)
            nxt[cur][c2i(c)] = unused++;
        cur = nxt[cur][c2i(c)];
        if (chk[cur]) return 0; // 입력된 문자열이 포함하는 다른 문자열이 존재하므로 일관성이 없음.
    }
    if (cur != unused - 1) return 0; // 입력된 문자열의 마지막 문자의 번호가 새로운 노드가 아니라면 
                                     // 입력된 문자열을 포함하는 다른 문자열이 존재하므로 일관성이 없음.
    chk[cur] = 1;
    return 1;   // 입력된 문자열이 다른 문자열을 포함하거나 포함되는 경우가 아닌경우이므로 일관성이 있음.
}


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        fill(chk, chk + MX, 0);
        for (int i = 0; i < MX; i++)
        {
            fill(nxt[i], nxt[i] + 10, -1);
        }
        unused = ROOT + 1;
        bool isvalid = 1;

        cin >> n;
        string s;
        while (n--)
        {
            cin >> s;
            if (!insert(s)) isvalid = 0;
        }
        if (isvalid) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}