[백준] 4358번: 생태학

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

initial

It is easy we just count the number of occurrence in a dict

diff between
f "{a} {b}" and '%s %.4f' %(a,b) ?
The latter is correct so maybe Im guessing the error has to do with the float? Oh so this f string is the latest way to print out with placeholders. It is more readable than with the modulo operator. BTW my f string is wrong it should be {b:.4f} for that float.

A more efficient way is using Counter.

revisited may 31st

Oh so i didnt think of counter but that could work. Btw deleting that empty string key step is necessary because splitting on newline characters might produce empty strings, especially if there are trailing newlines in the input. For example

sys.stdin.read() reads the whole input as 1 single string

"oak\npine\noak\nmaple\noak\npine\n"

you notice the new line character at the end. When we split it like split("\n"), empty string is also present like

["oak", "pine", "oak", "maple", "oak", "pine", ""]

I just thought like my initial approach where key is the name of tree and val is the number of occurrences of that tree. While taking in input, I want a total variable that counts total number of trees. Then we sort based on the dic’s key and preting result via f-string.

revisited june 27th

you can use the :.4f format specifier within the curly braces {} of the f-string. ALso, sorting .items() sorts the keys. If u want sort via value, you use lambda like

sorted(tree.items(),key =lambda x:x[1]

solution (ineff.)

ineff cuz im sorting based on the key. Wait but the counter approach also sorts.

import sys 
input = sys.stdin.readline
ans = 0
dic = {}
lst = []

while True:
    inp = input().strip()
    if not inp:
        break
    dic[inp] = dic.get(inp, 0) + 1
    ans += 1

for key, value in dic.items():
    lst.append([key, round((value / ans)*100, 4)])

lst.sort(key=lambda x: x[0])
for a,b in lst:
    print('%s %.4f' %(a,b))

solution (eff. using COunter)

import sys
from collections import Counter

trees = Counter(sys.stdin.read().split("\n"))
del trees[""]
total = sum(trees.values())
for tree, count in sorted(trees.items()):
    print(f"{tree} {100 * count / total:.4f}")

complexity

was sorting n long n? yep it is!

Your code reads input from the standard input until a blank line is encountered and then calculates the percentage distribution of each input string. Here's the time and space complexity analysis:

Time Complexity:

• The while loop iterates until a blank line is encountered, reading input and updating the dictionary and count.
• The for loop iterates over the dictionary items to calculate the percentage distribution.
• Sorting the list takes O(n log n) time, where n is the number of unique input strings.

Therefore, the overall time complexity is dominated by the sorting operation: O(n log n).

Space Complexity:

• The dictionary (dic) stores the frequency of each input string, and the list (lst) stores the results.

The space complexity is O(n), where n is the number of unique input strings.

Your code is efficient for typical use cases, and its performance will be reasonable unless you have a very large number of unique input strings.