생태학

문제 설명

나무들이 주어졌을 때, 해당 나무가 전체 나무에서 몇 %를 차지하는지 구하는 문제이다. 이때 출력은 알파벳 순으로 한다. 여기서 주의할 점은 전체 종의 몇 %가 아니라 입력받은 나무의 몇 %인지를 의미하는 것이다.

 

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

4358번: 생태학

문제 풀이

첫 번째 접근

문자열 집합과 마찬가지로 trie에 분류되어 있는 문제이다. 근데 굳이 trie로 풀 필요는 없을 거 같은...

 

아무튼 나는 trie로 문제를 풀었다. 

만일 만들어둔 trie 트리에 문자열이 있으면 해당 문자열(딕셔너리) 값을 하나 더해줬고 없으면 새로 추가해줬다. 이때 새로 추가한 문자열의 dic 값은 1로 초기화 했다.

 

그리고 dic 값을 key만 가지고 와서 정렬 한 다음에 정렬한 키 값대로 값을 하나 빼서 백분율을 계산해 소숫점 4자리 수까지 출력해줬다.

코드

import sys

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        cur = self.root
        for w in word:
            if w not in cur:
                cur[w] = {}
            cur = cur[w]
        cur['*'] = word

    def findWord(self, word: str) -> bool:
        cur = self.root
        for w in word:
            if w not in cur:
                return False
            cur = cur[w]
        return '*' in cur


trees = {}
t = Trie()
total = 0
while True:
    tree = sys.stdin.readline().rstrip()
    if tree == '':
        break
    total += 1
    if t.findWord(tree):
        trees[tree] += 1
    else:
        t.insert(tree)
        trees[tree] = 1

keyList = list(trees.keys())
keyList.sort()

for k in keyList:
    cal = trees[k]/total * 100
    print("%s %.4f" %(k, cal))