리트코드 649. Dota2 Senate

https://leetcode.com/problems/dota2-senate/description/

 

각 센터는 자신의 권리를 이용하여 상대방 센터의 권리를 박탈하거나, 동료만 남았을 경우 승리를 선언할 수 있다.

최종적으로는 한 편이 완전히 권리를 상실하게 되어 반대 편이 승리를 선언하게 된다.

문제 해설:

1. 큐(Queue) 사용:

이 문제를 해결하기 위한 핵심 아이디어는 각 센터가 상대방 센터를 얼마나 많이 "배제할 수 있는지" 추적하는 것이다.

이를 위해 두 개의 큐를 사용한다

• Radiant 큐: Radiant 센터의 인덱스를 저장
• Dire 큐: Dire 센터의 인덱스를 저장

2. 순차적으로 배제 반복:

• 각 센터는 순차적으로 자신의 권리를 사용하여 상대방의 투표권을 배제한다. 이때, 자신보다 인덱스가 앞선 상대방을 먼저 박탈하는 것이 유리하다. 왜냐하면 이들이 더 빨리 행동할 수 있기 때문이다.
• 두 큐에서 각각 하나씩 인덱스를 뽑아, 더 작은 인덱스를 가진 센터가 더 큰 인덱스를 가진 센터의 권리를 배제한다.
• 박탈 당하지 않은 센터는 다음 라운드에서 다시 행동할 수 있도록 큐에 다시 넣는다. 이때 인덱스에 센터 수(n)를 더하여 순환 구조를 만든다.

3. 승리 조건 검사:

• 한 큐가 비어있다면, 다른 큐에 있는 센터의 당은 승리를 선언할 수 있다.

예를 들어 senate = "RD"에서:

• R은 D를 박탈하고, 라운드가 끝나면 D는 더 이상 행동할 수 없다. 그러므로 R이 승리를 선언할 수 있다.

senate = "RDD"에서:

• 첫 번째 R은 바로 뒤의 D를 배제한다.
• 두 번째 D는 R을 배제할 기회가 없다 (첫 번째 D가 이미 배제당함).
• 세 번째 D는 남아 있는 유일한 센터로, 승리를 선언한다.

이 알고리즘은 O(n)의 시간 복잡도를 가진다. 각 센터는 최소 한 번씩 큐에 들어가므로, 모든 센터가 한 번씩 처리된다.

이는 입력 크기에 선형적으로 비례하는 풀이이다.

 

from collections import deque
class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        r = deque()
        d = deque()
        n = len(senate)

        for i, s in enumerate(senate):
            if s == "R":
                r.append(i)
            else:
                d.append(i)
        
        while r and d:
            ridx = r.popleft()
            didx = d.popleft()

            if ridx < didx:
                r.append(ridx + n)
            else:
                d.append(didx + n)
        
        if r:
            return "Radiant"
        else:
            return "Dire"