649. Dota2 Senate

 

📌 Problem Link :

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

 

✅ Accepted :

class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Character> queue = new ArrayDeque<>();
        int radiantCount = 0;
        int direCount = 0;

        // 초기 큐 구성 및 각 진영 카운트
        for (char ch : senate.toCharArray()) {
            queue.offer(ch);
            if (ch == 'R') radiantCount++;
            else direCount++;
        }

        int bannedRadiant = 0; // 다음에 등장하는 R을 제거할 권한 수
        int bannedDire = 0;    // 다음에 등장하는 D을 제거할 권한 수

        // 양쪽 진영이 남아있는 동안 반복
        while (radiantCount > 0 && direCount > 0) {
            char cur = queue.poll(); // null일 가능성 없음(문제 조건)
            if (cur == 'R') {
                if (bannedRadiant > 0) {
                    // 이 R은 금지되었으므로 제거 처리
                    bannedRadiant--;
                    radiantCount--;
                    continue;
                }
                // 이 R은 살아남아 라운드 끝에 다시 대기열에 들어가며,
                // 상대 진영(D) 중 하나를 금지할 권한을 얻음
                queue.offer(cur);
                bannedDire++;
            } else { // cur == 'D'
                if (bannedDire > 0) {
                    bannedDire--;
                    direCount--;
                    continue;
                }
                queue.offer(cur);
                bannedRadiant++;
            }
        }

        return radiantCount > 0 ? "Radiant" : "Dire";
    }
}

 

🧐 Review :

이 문제는 Radiant와 Dire 두 진영의 상원의원들이 서로를 제거해 나가며 최종 승자를 판별하는 시뮬레이션 문제입니다.

매 라운드마다 상원의원은 다른 상원의원의 권리를 박탈할 수 있고, 모든 상원의원이 같은 진영의 의원들로만 구성되어 있다면 승리를 선언할 수 있습니다.

 

핵심 아이디어: 큐(Queue)와 금지 권한

문제를 풀기에 앞서 상원의원들이 한 번 행동한 뒤 다시 라운드의 끝으로 돌아가며 반복되는 구조를 보고 자료구조 큐(Queue)가 떠올랐습니다. 큐를 사용하면 현재 차례인 의원이 행동 후 다시 대기열의 맨 뒤로 돌아가는 순환적인 라운드를 효과적으로 시뮬레이션할 수 있습니다.

추가적으로, 각 의원은 상대편의 다음 차례 의원을 금지할 권한을 가집니다. 이 금지 권한을 관리하기 위해 두 개의 변수를 사용합니다.

 

1. 초기 설정

큐 초기화: 입력 문자열 senate의 모든 상원의원을 순서대로 queue에 넣습니다. (R 또는 D)

카운트 초기화: radiantCount와 direCount 변수에 각 진영의 초기 상원의원 수를 저장합니다.

금지 권한 초기화: bannedRadiant (다음에 등장하는 R을 제거할 권한 수)와 bannedDire (다음에 등장하는 D을 제거할 권한 수)를 0으로 초기화합니다.

2. 라운드 시뮬레이션

그리고 양쪽 진영이 남아있는 동안 반복문( while (radiantCount > 0 && direCount > 0) )을 돌면서 큐에서 현재 차례의 상원의원을 꺼냅니다.

Case 1: cur이 'R'일 때

금지 여부 확인: bannedRadiant > 0인지 확인합니다.

금지되었다면: 이 'R'은 권한을 박탈당했으므로 bannedRadiant를 1 감소시키고, radiantCount를 1 감소시킨 후 continue하여 이번 라운드에서 제거됩니다.

금지되지 않았다면: 자신은 권한 행사 후 라운드의 끝으로 돌아가므로 큐의 맨 뒤에 다시 넣습니다. 상대 진영('D') 중 하나를 금지할 권한을 얻으므로 bannedDire를 1 증가시킵니다.

Case 2: cur이 'D'일 때

금지 여부 확인: bannedDire > 0인지 확인합니다. (로직은 'R'의 경우와 대칭적입니다.)

금지되었다면: bannedDire를 1 감소시키고, direCount를 1 감소시킨 후 제거됩니다.

금지되지 않았다면: 큐의 맨 뒤에 다시 넣습니다. 상대 진영('R')을 금지할 권한을 얻으므로 bannedRadiant를 1 증가시킵니다.

3. 최종 승자 판별

반복문은 한쪽 진영의 Count가 0이 될 때 종료됩니다. 즉, 더 이상 살아있는 (제거되지 않은) 상대 진영이 없다는 의미입니다.

최종적으로 radiantCount > 0이면 Radiant가 승리하며, 그렇지 않으면 Dire가 승리합니다.