У програмуванні багато чого можна робити по-різному. Підходи, методи, інструменти, оцінки якості варіантів, оптимізація — все це є цілим світом, різноманітним і захопливим. Пропоную сьогодні розглянути близьку, хоч і менш масштабну тему — взяти просту задачу і розв’язати її двома різними інструментами. Обидва, звичайно, мають свої переваги і недоліки, отже буде про що подумати тим, хто таке любить.
Задача: Кульки
(https://basecamp.eolymp.com/uk/problems/113)
У продавця повітряних кульок є n кульок. Кожна з них має деякий колір. Але зовсім недавно Три Товстуни видали наказ, який дозволяє торгувати кульками тільки якогось одного кольору. Щоб не порушувати закон, але при цьому і не втратити прибуток, продавець вирішив перефарбувати деякі із своїх кульок.
Напишіть програму для визначення мінімальної кількості перефарбувань.
Вхідні дані
В першому рядку задано кількість кульок n (1 ≤ n ≤ 100000). Другий рядок містить n цілих чисел, в межах від 1 до 9, що визначає колір кульок (1 - синій, 2 - зелений, 3 - голубий, 4 - червоний, 5 - рожевий, 6 - жовтий, 7 - сірий, 8 - чорний, 9 - білий).
Вихідні дані
Виведіть мінімальну кількість кульок, які необхідно перефарбувати, щоб всі кульки були одного кольору.
Приклади
Вхідні дані #1
4
3 1 2 1
Відповідь #1
2
Вхідні дані #2
4
4 9 9 6
Відповідь #2
2
Вхідні дані #3
1
1
Відповідь #3
0
Проаналізувавши приклади бачимо, що задача нескладна. Нам треба якомога менше кульок перефарбувати? Тоді давайте знайдемо, найбільшу кількість кульок одного кольору, а всі інші — перефарбуємо. Може бути варіант з повтором найбільшої кількості, наприклад 1 1 2 3 3. Але то не проблема, найбільша кількість кульок одного кольору — дві. А вже які ми будемо перефарбовувати, чи то 2 3 3 чи то 1 1 2 — для нашої задачі неважливо. В будь-якому варіанті перефарбувати доведеться три кульки.
В Python, як і в багатьох інших сучасних мовах програмування є можливість порахувати кількість елементів множини, що відповідає критерію. У нас в задачі всього дев’ять кольорів, тому давайте пошукаємо кількість кульок кожного кольору, знайдемо найбільшу з них і визначимо кількість кульок, які треба перефарбувати. Наприклад, так:
n = int(input())
b = [x for x in input().split()]
c1 = b.count('1')
c2 = b.count('2')
c3 = b.count('3')
c4 = b.count('4')
c5 = b.count('5')
c6 = b.count('6')
c7 = b.count('7')
c8 = b.count('8')
c9 = b.count('9')
print(n - max(c1, c2, c3, c4, c5, c6, c7, c8, c9))
Цей код здає задачу на 100%. Можна поговорити про оптимальність, про красу коду, посварити за дев’ять змінних, може було б гарніше тримати дані по кількостям в списку. Це на ваш розсуд. Як на мене — цей розв’язок простий і зрозумілий. Традиційне запитання адептів уніфікованих рішень «А якщо кольорів буде не дев’ять, а стомільонів?» пропоную не розглядати, бо то буде інша умова, відповідно, інша задача і даний код може бути неоптимальним, а то і непрацюючим взагалі. Ми ж розглядаємо не універсальну, а конкретну задачу.
Але ж в Python так багато смачного… Є відчуття, що код може бути гарніший. Може :) Давайте спробуємо Counter з модуля collections.
Припускаємо, що у нас є двадцять кульок різних кольорів, наприклад, таких
1 2 3 7 1 5 6 7 4 7 4 2 7 8 1 4 7 9 8 9
Давайте ми ці значення закинемо у список, а список віддамо в Counter. Що буде? Ось код:
from collections import Counter
n = int(input())
b = [x for x in input().split()]
c = Counter(b)
print(c)
Ось що буде:
Counter({'7': 5, '1': 3, '4': 3, '2': 2, '8': 2, '9': 2, '3': 1, '5': 1, '6': 1})
Кольору «7» — п’ять кульок, кольору «1» — три кульки, кольору «4» — три кульки і т.д.
І, очікувано, ми можемо визначити найбільш популярний колір:
print(c.most_common(1)[0][0])
І кількість кульок цього найпопулярнішого кольору:
print(c.most_common(1)[0][1])
Весь код розв’язку цієї задачі з використанням Counter:
from collections import Counter
n = int(input())
b = [x for x in input().split()]
c = Counter(b)
print(n - c.most_common(1)[0][1])
Як на мене, цей код теж має право на існування. Знайдуться ті, кому він подобається і ті, кому ні. Буде тема для обговорення. Може кому буде цікаво, в офіційному Python-help при поясненні Counter автори рахують кількість найпопулярніших слів в файлі hamlet.txt :)
Якщо вас зацікавила тема, у нас на «Плетиві» вже є стаття, де описано використання Counter, там розв'язується задача «Покер».
Успіхів!