BOJ 4358번 생태학 Python 문제 풀이
분류: Trie (트라이)
https://www.acmicpc.net/problem/4358
import sys
from collections import defaultdict
class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
self.cnt = 0
class Trie:
def __init__(self):
self.root = TrieNode()
self.total_cnt = 0
def insert_word(self, word: str) -> None:
node = self.root
for char in word:
node = node.children[char]
node.cnt += 1
self.total_cnt += 1
def show_cnt(self) -> None:
node = self.root
self.dfs(node, '')
def dfs(self, node: TrieNode, prefix: str) -> None:
if node.cnt > 0:
print("%s %.4f" % (prefix, (node.cnt / self.total_cnt * 100)))
for char in sorted(node.children.keys()):
self.dfs(node.children[char], prefix + char)
def main():
trie = Trie()
lines = sys.stdin.readlines()
for line in lines:
trie.insert_word(line.strip())
trie.show_cnt()
if __name__ == "__main__":
main()
Trie 자료구조를 구현하여 풀이하였다. 종 이름의 각 글자 별로 트라이 구조에 저장하고, 마지막 글자에는 cnt
속성에 1씩 더한다. 이렇게 하면 트라이를 탐색 할 때, 종 이름 끝 지점에서 몇 마리가 존재하는지 알 수 있다.
from collections import defaultdict
import sys
cnts = defaultdict(int)
total = 0
lines = sys.stdin.readlines()
for line in lines:
cnts[line.strip()] += 1
total += 1
for specy in sorted(cnts.keys()):
print("%s %.4f" % (specy, cnts[specy] / total * 100))
defaultdict를 이용하여 각 종의 수를 세고, 결과를 출력한다.