[Python] 백준 4358 생태학

문제

나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램 작성하기

 

 

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. (각 종은 30글자 이내 &

입력되는 종 개수 <= 10,000 & 입력되는 나무 개수 <= 1,000,000)

 

 

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력

 

 

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

4358번: 생태학

 

---

★Keypoint : 파이썬은 딕셔너리로!

 

리스트에 대입하는 것이 아닌 딕셔너리로 종과 그 개수를 저장한다.

 

 

 

<최종 CODE>

import sys

dic = {}
count = 0

while True:
    tree = sys.stdin.readline().strip()
    if not tree:
        break
    else:
        if tree in dic:
            dic[tree] += 1
        else:
            dic[tree] = 1
        count += 1

dic = sorted(dic.items())

for key, value in dic:
    print('%s %.4f' % (key, value / count * 100))

 

 

 

<CODE 설명>

딕셔너리 사용하면 쉽게 풀 수 있는 문제!

 

백준 문제 페이지 하단에 보면, 알고리즘 분류에 활용하면 좋은 자료구조 정보가 나와 있다.

 

파이썬과 같은 경우 딕셔너리는 해시의 특성을 이용하여 매우 빠르게 데이터를 검색하고 삽입할 수 있다. 해시 테이블은 평균적으로 O(1)의 시간 복잡도를 갖는다

반면에 트리는 주로 이진 검색 트리(Binary Search Tree)나 균형 트리(Balanced Tree)와 같은 형태로 사용되는데, 데이터를 정렬된 상태로 유지하기 때문에 검색이나 삽입 시에 일정한 시간이 걸리며, 평균적으로 O(log N)의 시간 복잡도를 갖는다. 균형 트리인 경우에는 O(log N)을 보장할 수 있지만, 일반적인 이진 검색 트리의 경우 최악의 경우에는 O(N)의 시간 복잡도가 발생할 수 있다.

 

따라서 딕셔너리가 가장 효율적!

 

 

※while문의 else문 안에 있는 if, else 문 대신 try 와 except문을 사용하면 조금 더 시간이 단축된다.