649. Dota2 Senate

LeetCode задача 649

Задача

В игре Dota2, сенат состоит из двух партий: партии “Radiant” и партии “Dire”. Сенат решает, когда будет следующая игра, и каждый сенатор может голосовать за бан одного из сенаторов из другой партии.

Забаненные сенаторы не могут делать действий и не участвуют в процессе подготовки следующего раунда.

Предположим, у нас есть строка “RRDDD”. Здесь первый сенатор принадлежит партии Radiant, второй тоже к Radiant, третий, четвертый и пятый к Dire. Сначала первый сенатор Radiant делает ход, затем первый сенатор Dire, и так далее.

Когда сенатор делает ход, он может забанить сенатора из другой партии. Если он это делает, этот сенатор больше не участвует в игре. Цель — оставить в игре только сенаторов своей партии.

Задача определить, какая партия победит и объявит игру.

Подсказки

Использовать очередь для хранения позиций сенаторов из каждой партии. Позиции важны, потому что по условию задачи сенаторы “голосуют” в заданном порядке.

Подход

Важно понимать, что сенаторы действуют в определенной последовательности, и это влияет на исход игры.

1. Мы можем определить, какой сенатор голосует первым, путем нахождения его индекса в строке senate.
2. После того, как мы определили кто голосует первым, мы знаем, что задача первого забанить сенатора из другой партии, а это означает что сам он продолжает играть дальше и перейдет на следующий раунд.
   1. т.е. Если порядок сенаторов такой: RDD, то первый сенатор R банит первого сенатора D и переходит на второй раунд. В строке это бы отобразилось таким образом: R~~~~DDR. И теперь начинается ход второго оставшегося сенатора D, который забанит первого сенатора R.
3. Таким образом, мы можем определить текущий индекс/позицию каждого сенатора и переставлять их на конец очереди если они голосуют.
   1. А во время этого хода сенатор противоположной партии банится.

Как определить, кто сейчас голосует и чей ход? - Сравнить индексы каждого сенатора из разных партий. Чей индекс(позиция) раньше, тот и голосует. Соответсвенно, сенатор под самым маленьким индексом из другой партии будет забанен.

Алгоритм

1. Создаем две очереди для хранения индексов(порядка) сенаторов обеих партий.
   1. Итерируем по всем сенаторам и добавляем их в соответствующие очереди.
2. Пока обе очереди не пусты:
   • Сравниваем первых(в очереди) сенаторов в каждой очереди.
   • Забаним сенатора с большим до следующего хода. Как? - не добавим его в конец очереди для следующего раунда.
   • Сенатор, который не был забанен, возвращается в конец очереди (его индекс увеличивается на общее количество сенаторов)
3. В результате остается одна очередь - победитель. Когда одна из очередей станет пустой, партия, чья очередь осталась, побеждает.

Решение

from collections import deque

def predictPartyVictory(senate: str) -> str:
    radiant = deque()
    dire = deque()

    # Заполнение очередей
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)

    n = len(senate)

    # Процесс голосования
    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()
        
        # Сенатор с меньшим индексом банит сенатора с большим индексом
        # и переходит во второй раунд (текущий индекс + всего индексов в раунде)
        if r < d:
            radiant.append(r + n)
        else:
            dire.append(d + n)
    
    return "Radiant" if radiant else "Dire"