BAEKJOON#5052電話番号リスト(文字列)-python
電話番号リスト
出典:白駿#5052
タイムアウトメモリ制限毎秒256 MB
質問する
電話番号のリストを表示します.この場合、リストが一致しているかどうかを判断するプログラムを作成します.
電話番号リストを一致させるには、1つの番号が別の番号の接頭辞であってはならない.
例えば、電話番号リストが次のような場合を考えてみましょう.
このような状況では、善英に電話することはできない.ソンヨンが電話を取って、番号の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スペースを作りました.Graph
クラスは探索の初めにadjListを使用することを発表し、同様に0~9に達することができると考え、10余りのスペースを割り当てた.insertEdge
関数により、最初の数字がなければノードを生成し、その数字をインデックスに入れる.これにより,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))
Reference
この問題について(BAEKJOON#5052電話番号リスト(文字列)-python), 我々は、より多くの情報をここで見つけました https://velog.io/@nathan29849/BAEKJOON-5052번-전화번호-목록-문자열-pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol