2

Частотный анализ – 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 сек. Помогите, пожалуйста, как-нибудь сократить код или найти более оптимальное решение данной задачи.

1 ответ 1

2

я бы делал это приблизительно так:

ввод:

N = int(input())
text = " ".join(input() for _ in range(N))

или менее читабельный, но более короткий вариант:

text = " ".join(input() for _ in range(int(input())))

подсчет слов:

res = {}    
for word in text.strip(",.!?:;").lower().split():
    res[word] = res[word] + 1 if word in res else 1

for word,cnt in sorted(res.items(), key=lambda x: (-x[1], x[0])):
    print(word.capitalize())

вывод:

Грека
В
Рак
Реку
Руку
Видит
Греку
Ехал
За
Реке
Сунул
Цап
Через
16
  • 1
    strip('.,!?:;')
    – splash58
    28 апр 2020 в 19:48
  • тогда, наверное еще делить по дефису надо было бы
    – splash58
    28 апр 2020 в 20:01
  • @splash58, даже не знаю... стоит ли делить слово все-таки на все и таки 28 апр 2020 в 20:02
  • ну да. я тоже не знаю
    – splash58
    28 апр 2020 в 20:03
  • @splash58, вот - решил проверить... ;) В общем, скорее это надо считать одним словом и поэтому ваш вариант вполне валиден 28 апр 2020 в 20:04

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.