https://www.acmicpc.net/problem/20291
initial
Very easy we just use split(“.”) to split into a list of strings and use a dictionary to count number of occurrences. We want the ascending order of keys so we use sorted(), which takes an iterable like tuple,list or dict (i didnt know dict can use this too) and sort.
solution
from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
dic = defaultdict(int)
for _ in range(n):
hola = input().strip()
hola_lst = hola.split(".")
dic[hola_lst[1]] += 1
for key, val in sorted(dic.items()):
print(f'{key} {val}')complexity
n log n cuz sort time?
Time Complexity:
Reading input in the loop (for _ in range(n)): O(n), where n is the number of iterations.
Splitting the input string (hola.split(".")): O(M), where M is the length of the input string.
Updating the defaultdict (dic[hola_lst[1]] += 1): O(1), constant time operation.
Sorting the dictionary items (sorted(dic.items())): O(K log K), where K is the number of unique keys in the dictionary. This operation is dominated by the sorting step.
Iterating through the sorted items in the loop: O(K), where K is the number of unique keys.
The overall time complexity is O(n + K log K + M), where n is the number of iterations, K is the number of unique keys, and M is the length of the input string.
Space Complexity:
Creating the defaultdict (defaultdict(int)): O(K), where K is the number of unique keys.
Creating the hola_lst list: O(M), where M is the length of the input string.
Creating the dictionary (dic): O(K), where K is the number of unique keys.
The overall space complexity is O(K + M).
In summary:
Time Complexity: O(n + K log K + M)
Space Complexity: O(K + M)
