電話番号リスト

出典:白駿#5052
タイムアウトメモリ制限毎秒256 MB

質問する

電話番号のリストを表示します.この場合、リストが一致しているかどうかを判断するプログラムを作成します.
電話番号リストを一致させるには、1つの番号が別の番号の接頭辞であってはならない.
例えば、電話番号リストが次のような場合を考えてみましょう.

緊急電話:911

勤務:976259999

善英:91125426
このような状況では、善英に電話することはできない.ソンヨンが電話を取って、番号の3番目の位置を押した瞬間、緊急電話がかかってくるからだ.したがって、このリストは一致しないリストです.

入力

第1行は、試験例の個数tを与える.(1≦t≦50)各試験例の第1行には、電話番号の数nが与えられる.(1≦n≦10000)以下のn行には、リストに含まれる電話番号が与えられる.電話番号の長さは最大10桁で、リストの2つの電話番号が同じではない場合.

しゅつりょく

各テストケースについて,一致するリストであればYES,そうでなければNOを出力する.

I/O例

入力例1

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

サンプル出力1

NO
YES

に答える

思考と解答説明

最初は、短い文字列が長い文字列の前の部分に属するかどうかをダブルfor文で判断するだけです.

もちろん間違った答えです.(タイムアウト)

本当に思い出せないので、質問検索ページを見て、Trie?アルゴリズムで解く.

実際には、対応するアルゴリズムを見つけて完璧な練習をすることができますが、自尊心は許されません.

そこで,ツリーアクセスを用いた事実だけに注目し,コードを自分で作成した.

コアは、文字列の終了時にflagを植え込み、他の文字列をツリーに挿入したときにflagをスキップしたかどうかを判断することです.

説明が難しい場合は、下図を参照してください.

まず、Nodeクラスでnextスペースを作りました.

番号は0から9の間で可能なので、10個のスペースが割り当てられている.

flagもインプラントし、初期値をfalseに設定します.

Graphクラスは探索の初めにadjListを使用することを発表し、同様に0~9に達することができると考え、10余りのスペースを割り当てた.

・insertEdge関数により、最初の数字がなければノードを生成し、その数字をインデックスに入れる.

最初の数字の空間にノードが存在している場合は、それに沿ってノードを下りさせます.

flagは途中で会うと止まるように作られている.

これにより,1つの番号ではフィルタリングができないため,1つの文字列が入るときにflagを植え込むif文が加わる.

最近,文字列問題を解く際に感じたのは,多様な資料構造による可視化や逆探索により,問題により容易に触れることができることである.

多くの不足があったが、結局は答えを見ずに自分でコードを書くきっかけになり、これからも様々な資料構造を一緒に考えなければならない.

python code

# 백준 5052번 전화번호 목록
from sys import stdin
input = stdin.readline

class Node:
    def __init__(self, node):
        self.node = node
        self.next = [None]*10
        self.flag = False

class Graph:
    def __init__(self):
        self.adjList = [0] * 10
    
    def insertEdge(self, string):
        x = int(string[0])
        if self.adjList[x] == 0:
            new = Node(x)
            self.adjList[x] = new
   
        
        temp = self.adjList[x]
        if len(string) == 1:
            temp.flag = True
        else:
            if temp.flag == True:
                return False
        for i in range(1, len(string)):
            S = int(string[i])
            if temp.next[S] is None:
                w = Node(S)
                temp.next[S] = w
            else:
                if temp.next[S].flag != False:
                    return False
            if i == len(string)-1: # 마지막 원소라면
                temp.next[S].flag = True
            temp = temp.next[S]
        return True
                

def solution(phonebook):
    phonebook.sort()
    n = len(phonebook)
    g = Graph()
    for number in phonebook:
        result = g.insertEdge(number)
        if result != True:
            return "NO"
    return "YES"


    # 시간 초과
    # for i in range(n):
    #     for j in range(i+1, n):
    #         m = len(phonebook[i]) 
    #         if len(phonebook[i]) < len(phonebook[j]):
    #             if phonebook[j][:m] == phonebook[i]:
    #                 return "NO"
    # return "YES"


t = int(input())
for x in range(t):
    n = int(input())
    phonebook = []
    for i in range(n):
        phonebook.append(input().rstrip())
    print(solution(phonebook))