🤔접근

한 전화번호가 또 다른 전화번호를 포함하는 경우가 있다면 일관성이 없다고 볼 수 있다. 전화번호의 길이는 길어야 10자리이고, 1 ≤ t(테스트 케이스 수) ≤ 50, 1 ≤ n(전화번호의 수) ≤ 10000 이다. 따라서 삽입/탐색/삭제 시간복잡도가 O(S) [S: 문자열 길이, 여기서는 전화번호의 길이]인 트라이 자료구조를 사용하여 풀이할 수 있다.

🤓풀이

1

3

91125426

911

97625999

위와 같이 예시의 테스트케이스와 다른 순서로 입력이 들어오는 경우,

91125426 (911을 포함하지만 먼저 입력으로 들어옴)

911

풀이와 같이, '*'(문자열의 끝)을 찾자마자 return 해버리면 출력이 달라질 수 있다. 따라서, 길이에 따른 오름차순 정렬을 먼저 수행해야 한다.

import sys
input=sys.stdin.readline

class Trie():
    head={}

    def add(self,word):
        cur=self.head

        for ch in word:
            if '*' in cur:
                return False
            if ch not in cur:
                cur[ch]={}
            cur=cur[ch]
        cur['*']=True

        return True

trie=Trie()
for _ in range(int(input().rstrip())):
    # Test Case마다 루트, 플래그 초기화 유의
    trie.head={}
    FLAG=True
    arr=[]

    for _ in range(int(input().rstrip())):
        arr.append(input().rstrip())
        
    # 길이에 따른 오름차순 정렬 필수
    arr.sort(key=lambda x:len(x))

    for a in arr:
        if not trie.add(a):
            FLAG=False

    if FLAG:
        print('YES')
    else:
        print('NO')