[Python] 백준 4358 - 생태학 문제 풀이

Overview

BOJ 4358번 생태학 Python 문제 풀이
분류: Trie (트라이)

문제 페이지

https://www.acmicpc.net/problem/4358

풀이 코드 1 - Trie

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씩 더한다. 이렇게 하면 트라이를 탐색 할 때, 종 이름 끝 지점에서 몇 마리가 존재하는지 알 수 있다.

풀이 코드 2 - defaultdict

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를 이용하여 각 종의 수를 세고, 결과를 출력한다.