[5052번] 전화번호 목록

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL :: http://www.crocus.co.kr/604

2. 정렬 

이 문제는 접두사를 이용하여 전화번호를 누르기 전에 다른 전화에 걸리는지 확인해야 한다.

따라서 크기가 작은 순으로 정렬을 해주고,

크기가 작은 것 하나를 먼저 맵에 넣어둔다.

이후 for문으로 그다음 크기의 전화번호를 확인한다. 이때 전화번호는 최대 10의 길이를 가지니 1부터 10까지

substring을 확인하여 맵에 이미 있는지 확인한다. 만약 substring이 존재한다면 번호를 누르는 도중 전화가 걸린다는 의미이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
 
using namespace std;
 
bool comp(const string &a, const string &b)
{
    return a.size() < b.size();
}
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        int n;
        scanf("%d", &n);
 
        string str[10001];
        map<string, bool> mp;
 
        for (int i = 0; i < n; i++)
        {
            char tmp[12];
            scanf("%s", tmp);
            str[i] = tmp;
        }
        sort(str, str + n, comp);
 
        mp[str[0]] = true;
 
        bool ans = true;
        for (int i = 1; i < n; i++)
        {
            for (int len = 1; len <= 10; len ++)
            {
                if (mp[str[i].substr(0, len)] == 1)
                {
                    ans = false;
                    break;
                }
            }
            mp[str[i]] = true;
        }
 
        if (ans)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>