Частотный анализ – 1. Условие:
Дан текст на русском языке. Посчитайте, сколько раз встречается в тексте каждое слово.
Слово — это последовательность русских букв. Кроме слов, в тексте могут присутствовать пробелы и знаки препинания («,», «.», «!», «?», «:» и «;»). Других символов в тексте нет.
Слова необходимо сравнивать с точностью до регистра. То есть «Привет» и «привет» — это одно и то же слово, а вот «рыба», «рыбы» и «рыбу» — три разных.
Формат ввода:
В первой строчке задано одно целое число N (1 ≤ N ≤ 1000) — количество строк в тексте. В следующих N строках приведён сам русский текст. Текст состоит из русских букв, пробелов и знаков препинания: «,», «.», «!», «?», «:» и «;». Длина текста не превышает 100 000 символов.
Формат вывода:
Выведите слова исходного текста, упорядоченные по убыванию количества их попаданий в текст. В случае, если два слова встречаются в тексте одинаковое количество раз, выведите их в лексикографическом порядке.
Каждое слово нужно вывести в отдельной строке. Первая буква слова должна быть заглавной (даже если она не была заглавной в исходном тексте), остальные — строчными.
Пример
Ввод:
2
Ехал Грека через реку. Видит Грека в реке рак.
Сунул Грека руку в реку, рак за руку Греку цап.
Вывод:
Грека
В
Рак
Реку
Руку
Видит
Греку
Ехал
За
Реке
Сунул
Цап
Через
В учебных целях не надо использовать функции, импорт модулей, классы. Решить задачу надо используя множества, списки, словари и их методы.
У меня получился такой код:
words_dict = {}
sentences1 = [input().split() for i in range(int(input()))]
sentences = [j.strip('!?:;,.').capitalize() for i in sentences1 for j in i]
for i in sentences:
words_dict[i] = words_dict[i] + 1 if i in words_dict else 1
keys = list(words_dict.keys())
values = list(words_dict.values())
for i in range(len(keys) - 1):
for j in range(len(keys) - i - 1):
if keys[j] > keys[j + 1]:
keys[j], keys[j + 1] = keys[j + 1], keys[j]
values[j], values[j + 1] = values[j + 1], values[j]
for i in range(len(keys) - 1):
for j in range(len(keys) - i - 1):
if values[j] < values[j + 1]:
values[j], values[j + 1] = values[j + 1], values[j]
keys[j], keys[j + 1] = keys[j + 1], keys[j]
print('\n'.join(keys))
Он пе проходит по времени, при вводе 900 строк код выполняется за 1.089 секунд моё решение не принимают, ограничение по времени 1 сек. Помогите, пожалуйста, как-нибудь сократить код или найти более оптимальное решение данной задачи.