[Python] 백준 - 5670 Trie

풀이

 

class Node(object):
    def __init__(self, key):
        self.key = key
        self.children = {}
        self.isLeaf = False
    
class Trie(object):
    def __init__(self):
        self.root = Node(None)
    
    def insert(self, word):
        curr_node = self.root
        for chr in word:
            if chr not in curr_node.children:
                curr_node.children[chr] = Node(chr)
            curr_node = curr_node.children[chr]
        curr_node.isLeaf = True


    def search_count(self, word):
        curr_node = self.root

        cnt = 0
        for chr in word:
            if chr in curr_node.children:
                curr_node = curr_node.children[chr]
                if len(curr_node.children) > 1 or curr_node.isLeaf:
                    cnt +=1
        return cnt
                       

def main():
    try : 
        while True:            
            N = int(input().strip())
            words = []
            t = Trie()
            for _ in range(N):
                string = input()
                words.append(string)
                t.insert(string)
            sum = float(0)
            for word in words:
                sum += t.search_count(word) 
            ans = round(sum/len(words), 2)
            print(format(ans, "0.2f"))
    except:
        pass

if __name__ == '__main__':
    main()