[LeetCode_649] Dota2 Senate(Python)

https://leetcode.com/problems/dota2-senate/description/?envType=study-plan-v2&envId=leetcode-75

문제

---

코드1

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        dq = deque([])
        rq = deque([])
        for i in range(len(senate)):
            if senate[i] == 'D':
                dq.append(i)
            else:
                rq.append(i)
        idx = 0
        while True:
            if idx in dq:
                if rq:
                    x = rq.popleft()
                    dq.append(dq.popleft())
                else:
                    return 'Dire'
            elif idx in rq:
                if dq:
                    x = dq.popleft()
                    rq.append(rq.popleft())
                else:
                    return 'Radiant'
            idx = (idx + 1) % len(senate)
                

        

코드 2

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        dq = deque([])
        rq = deque([])
        for i in range(len(senate)):
            if senate[i] == 'D':
                dq.append(i)
            else:
                rq.append(i)
        idx = len(senate)
        while dq and rq:
            d, r = dq.popleft(), rq.popleft()
            if d > r:
                rq.append(idx)
            else:
                dq.append(idx)
            idx += 1
        return 'Radiant' if rq else 'Dire'
            

---

Idea 1

• 시간복잡도가 비효율적인 코드 -> idx를 1씩 증가하며 큐 내부를 일일이 확인하는 것이 문제

Idea 2

• 두 개의 큐 중 하나라도 빌때까지 반복 -> d, r중에 오른쪽에 있는 값을 제거하고, 남아있는 정수는 전체크기 + 1씩 증가해가며 다시 큐에 추가