[백준 5052] 전화번호 목록

▶ 문제 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

▶ Trie란?

insert함수를 이용해 단어들을 삽입한뒤, 단어들의 알파벳끼리 연결해서 트리형태로 만든다.

1) 단어가 트리내에 존재하는지 확인해보거나(search함수)

2) 주어진 단어를 prefix로 가지는 단어의 배열을 리턴해준다(starts_with함수)

3) 시간복잡도는 O(m)이다.

class Node:
    def __init__(self, key,data=None):
        self.key = key     # 단어의 글자 하나를 담는곳
        self.data = data   # 사실상 마지막 글자인지 나타내주는 flag
                           # 마지막 글자의 경우에 단어 전체를 data필드에 저장하고,
                           # 아닌 경우는 null로 둔다.
        self.children = {} # dict

    # 즉, Jack의 경우 J, a, c, k 에서 마지막 글자인 K노드의 data필드에만
    # "Jack"이 들어가고, 그 외 노드의 data필드는 널(None)이다


    # trie구조를 예쁘게 출력해주는 함수 (http://cd4761.blogspot.com/2017/02/trie-1.html)
    def __str__(self, depth=0): 
        s = []
        for key in self.children:
            s.append('{}{} {}'.format(' ' * depth, key or '#', '\n' 
                                      + self.children[key].__str__(depth + 1)))

        return ''.join(s)
    
class Trie:
    def __init__(self):
        self.root = Node('') # key=None

    def __str__(self, depth=0):
        return self.root.__str__()
    
    # 트라이에 문자열을 삽입
    def insert(self, inputString): # print, python, pytorch
        curr_node = self.root # 루트부터 시작 

        for c in inputString: # p, y, t, h, o, n
            if c not in curr_node.children: # 알파벳이 자식에 존재하지 않으면 
                curr_node.children[c] = Node(c)
            curr_node = curr_node.children[c] # curr_node를 업데이트 

        # inputString의 마지막 글자 차례이면,
        # 노드의 data필드에 inputString문자열 전체를 저장한다.
        curr_node.data = inputString  


    # inputString이 트라이에 존재하는지 여부 반환
    def search(self, inputString):
        curr_node = self.root # 루트부터 시작

        for c in inputString:
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
            else:
                return False # 없으면 즉시 False반환 

        # inputString의 마지막 글자에 도달했을때,
        # curr_node에 data가 있다면 inputString이 트라이 안에 존재하는것!
        
        if curr_node.data != None:
            return True

    # 주어진 prefix로 시작하는 단어들을,
    # BFS로 트라이에서 찾아 리스트 형태로 반환
    def starts_with(self, prefix): # pr
        curr_node = self.root # 루트부터 시작 
        result = []
        subtrie = None

        # 트라이에서 prefix를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        
        for c in prefix: # prefix 알파벳 한글자씩 비교 ( p , r )
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
                subtrie = curr_node # subtrie로 설정
                print(prefix, '의 알파벳: [',c,']일때 <subtrie>')
                print(subtrie)
            else:
                return None # 없으면 즉시 함수 종료

        # BFS로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        
        # 여기 이해 X
        queue = list(subtrie.children.values()) # queue = [Node(i)]
        print('초기 큐 길이=', len(queue))
        while queue:
            curr = queue.pop()
            print('ㅡㅡㅡㅡㅡㅡㅡ')
            print('큐에서 꺼낸 <curr>')
            print(curr)
            if curr.data != None: # curr.data는 마지막노드에만 존재한다.(완전한 단어형태로 저장되어있다)
                result.append(curr.data) # curr.data = 완전한 단어
                print()
                print('>>>result=', result)
                print()
            queue += list(curr.children.values()) # queue = [Node(n)]

        return result


# 테스트 코드
trie = Trie()
trie.insert('print')
trie.insert('python')
trie.insert('pytorch')
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
if trie.search('python'):
    print('python단어 존재!')
if trie.search('java'):
    print('java단어 존재!')
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')

print('<전체 trie구조>')
print(trie)

print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
trie.starts_with('pr') # ['print']
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
trie.starts_with('pyt') # ['pytorch', 'python']


# 출처 : https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

 

▶ 5052 전화번호 목록 풀이

class Node:
    def __init__(self, key,data=None):
        self.key = key     # 단어의 글자 하나를 담는곳
        self.data = data   # 사실상 마지막 글자인지 나타내주는 flag
                           # 마지막 글자의 경우에 단어 전체를 data필드에 저장하고,
                           # 아닌 경우는 null로 둔다.
        self.children = {} # dict

    # 즉, Jack의 경우 J, a, c, k 에서 마지막 글자인 K노드의 data필드에만
    # "Jack"이 들어가고, 그 외 노드의 data필드는 널(None)이다

    # trie구조를 예쁘게 출력해주는 함수 (http://cd4761.blogspot.com/2017/02/trie-1.html)
    def __str__(self, depth=0): 
        s = []
        for key in self.children:
            s.append('{}{} {}'.format(' ' * depth, key or '#', '\n' 
                                      + self.children[key].__str__(depth + 1)))

        return ''.join(s)
    
    
class Trie:
    def __init__(self):
        self.root = Node('') # key=None

    def __str__(self, depth=0):
        return self.root.__str__()
    
    # 트라이에 문자열을 삽입
    def insert(self, inputString): # print, python, pytorch
        curr_node = self.root # 루트부터 시작 

        for c in inputString: # p, y, t, h, o, n
            if c not in curr_node.children: # 알파벳이 자식에 존재하지 않으면 
                curr_node.children[c] = Node(c)
            curr_node = curr_node.children[c] # curr_node를 업데이트 

        # inputString의 마지막 글자 차례이면,
        # 노드의 data필드에 inputString문자열 전체를 저장한다.
        curr_node.data = inputString  


    # inputString이 트라이에 존재하는지 여부 반환
    def search(self, inputString):
        curr_node = self.root # 루트부터 시작

        for c in inputString:
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
            else:
                return False # 없으면 즉시 False반환 

        # inputString의 마지막 글자에 도달했을때,
        # curr_node에 data가 있다면 inputString이 트라이 안에 존재하는것!
        
        if curr_node.data != None:
            return True

    # 주어진 prefix로 시작하는 단어들을,
    # BFS로 트라이에서 찾아 리스트 형태로 반환
    def starts_with(self, prefix): # pr
        curr_node = self.root # 루트부터 시작 
        result = []
        subtrie = None

        # 트라이에서 prefix를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        
        for c in prefix: # prefix 알파벳 한글자씩 비교 ( p , r )
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
                subtrie = curr_node # subtrie로 설정
                #print(prefix, '의 알파벳: [',c,']일때 <subtrie>')
                #print(subtrie)
            else:
                return None # 없으면 즉시 함수 종료

        # BFS로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        
        # 여기 이해 X
        queue = list(subtrie.children.values()) # queue = [Node(i)]
        #print('초기 큐 길이=', len(queue))
        while queue:
            curr = queue.pop()
            #print('ㅡㅡㅡㅡㅡㅡㅡ')
            #print('큐에서 꺼낸 <curr>')
            #print(curr)
            if curr.data != None: # curr.data는 마지막노드에만 존재한다.(완전한 단어형태로 저장되어있다)
                result.append(curr.data) # curr.data = 완전한 단어
                #print()
                #print('>>>result=', result)
                #print()
            queue += list(curr.children.values()) # queue = [Node(n)]

        return result



T = int(input())
for _ in range(T):

    trie = Trie() # Trie class 초기화  
    
    n = int(input())
    lst = []
    
    for _ in range(n):
        word = str(input())
        lst.append(word)
        trie.insert(word)
    #print(lst)
    #print(trie)

    flag = 0
    for a in lst:
        t = trie.starts_with(a)
        #print(t)
        if len(t)>0:
            flag = 1
            break
    if flag == 1:
        print('NO')
    else:
        print('YES')