[BOJ] [Python] 4358 : 생태학

트라이를 이용해 해결했다. 시간복잡도는 O(N * M)이다. (N : 최대 그루 수, M : 최대 이름 길이)

입력이  N은 1,000,000, M은 30이니까, 30,000,000으로 1초내 수행이 가능하다.

 

(문자열 탐색 알고리즘을 사용하지 않으면 O(N * N * M)이라 시간 초과이다.)

 

 

import sys


class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data is not None:
            return True

        else:
            return False


dp = {}
trie = Trie()

cnt = 0

while True:
    name = sys.stdin.readline().rstrip()

    if not name:
        break

    cnt += 1
    if trie.search(name):
        dp[name] += 1

    else:
        trie.insert(name)
        dp[name] = 1

dp = sorted(dp.items())

for val in dp:
    print("%s %.4f" % (val[0], val[1] / cnt * 100))

 

 

1. rstrip 함수는 문자열 끝 공백을 제거해준다.

 

 

2. 몇 그루의 나무가 들어올지 몰라서, 공백을 제거한 입력상태가 ''이라면 입력을 멈춘다.

search 함수를 이용해 동일한 문자열이 있는지 찾고, 있으면 해당 나무 종의 그루 수를 1개 더해준다.

없으면 해당 나무 종의 그루 수를 1로 해준다. 

 

출력할 때, 전체에서 각 나무의 종이 차지하는 백분율을 구해야 한다. 

( 일부값 % 전체값 X 100 )

 

 

3. 이때 round 함수를 쓰면 '틀렸습니다'가 나온다.

round 함수의 방식이 좀 독특하기 때문이다. Python 공식문서의 round 함수 설명을 보자.

 

"float에 대한 round()의 동작은 예상과 다를 수 있습니다: 예를 들어, round(2.675, 2)는 2.68 대신에 2.67을 제공합니다. 이것은 버그가 아닙니다: 대부분의 십진 소수가 float로 정확히 표현될 수 없다는 사실로부터 오는 결과입니다."

 

부동 소수점 산술의 문제점 및 한계에 대해 더 알아보자.

 

부동 소수점 숫자는 하드웨어에서 이진 소수로 표현된다.

그런데 십진 소수는 정확하게 이진 소수로 표현할 수 없다.

 

쉬운 예로 이해해보자.

 

1/3을 십진 소수로 표현하면 0.3 -> 0.33 -> 0.333이다.

아무리 자릿수를 늘려도 정확하게 1/3이 되지 않는다. 하지만 더 가까운 근사치가 된다.

 

십진 부동 소수점 숫자가 하드웨어에 저장될 때는 이진 부동 소수점 수로 근사 될 뿐이다.

 

따라서 round(2.675, 2)가 2.68이 안 나오는 이유도 이 때문이다.

 

 

4. 다른 사람 코드 분석

 

 

import sys
from collections import defaultdict

cnt = 0
tree = defaultdict(int)

while True:
    tmp = sys.stdin.readline().rstrip()
    if not tmp:
        break
    tree[tmp] += 1
    cnt += 1

tree = sorted(tree.items())

for name, num in tree:
    print("%s %.4f" % (name,num/cnt*100))

 

 

 

 

defaultdict는 딕셔너리를 만드는 dict 클래스의 서브 클래스이다.

defaultdict 함수에 주어진 인자를 타입으로 딕셔너리의 초깃값을 지정한다.

 

위 코드는 dict를 이용했고 시간복잡도는 O(N)이다.