leetcode link

Description

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

• Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
• Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

---

이 문제는 Dota2 세계에서 발생하는 두 정당, Radiant와 Dire 사이의 갈등에 관한 것입니다. Dota 2 상원은 두 정당의 의원들로 구성되어 있습니다. 이제 상원은 도타2 게임의 변경 사항을 투표로 결정하고자 합니다. 이 투표는 라운드 기반으로 진행되며, 각 상원의원은 다음의 두 권리 중 하나를 행사할 수 있습니다:

• 한 상원의원의 권리 금지: 한 상원의원은 다른 상원의원이 이번 및 이후 모든 라운드에서 모든 권리를 잃게 할 수 있습니다.
• 승리 선언: 이 상원의원이 여전히 투표할 권리가 있는 상원의원이 모두 같은 파티에서 왔다고 판단하면, 승리를 선언하고 게임의 변경을 결정할 수 있습니다.

상원의원의 소속 파티를 나타내는 문자열 senate가 주어지며, 'R'과 'D' 문자는 각각 Radiant 파티와 Dire 파티를 나타냅니다. 만약 n명의 상원의원이 있다면, 주어진 문자열의 크기는 n이 될 것입니다.

라운드 기반 절차는 주어진 순서대로 첫 번째 상원의원부터 마지막 상원의원까지 시작됩니다. 이 절차는 투표가 끝날 때까지 지속됩니다. 권리를 잃은 모든 상원의원들은 절차 동안 건너뛰어집니다.

모든 상원의원이 충분히 현명하다고 가정하고, 자신의 파티를 위한 최선의 전략을 사용할 것입니다. 결국 어느 파티가 승리를 선언하고 Dota2 게임을 변경할지 예측하세요. 출력값은 "Radiant" 또는 "Dire"여야 합니다.

예시 1:

입력: senate = "RD"
출력: "Radiant"
설명: 첫 번째 상원의원은 Radiant에서 왔으며, 라운드 1에서 다음 상원의원의 권리를 금지시킬 수 있습니다. 그리고 두 번째 상원의원은 그의 권리가 금지되었기 때문에 더 이상 권리를 행사할 수 없습니다. 라운드 2에서, 첫 번째 상원의원은 투표할 수 있는 유일한 사람이기 때문에 승리를 선언할 수 있습니다.

예시 2:

입력: senate = "RDD"
출력: "Dire"
설명: 첫 번째 상원의원은 Radiant에서 왔으며, 라운드 1에서 다음 상원의원의 권리를 금지시킬 수 있습니다. 그리고 두 번째 상원의원은 그의 권리가 금지되었기 때문에 더 이상 권리를 행사할 수 없습니다. 세 번째 상원의원은 Dire에서 왔으며, 라운드 1에서 첫 번째 상원의원의 권리를 금지시킬 수 있습니다. 라운드 2에서, 세 번째 상원의원은 투표할 수 있는 유일한 사람이기 때문에 승리를 선언할 수 있습니다.

제약 조건:

• n == senate.length
• 1 <= n <= 10^4
• senate[i]는 'R' 또는 'D'입니다.

Solution

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.stream.Collectors;

class Solution {
    public String predictPartyVictory(String senate) {
        Deque<Character> deque = senate.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.toCollection(ArrayDeque::new));

        int radiantBanCount = 0;
        int direBanCount = 0;
        while (radiantBanCount != deque.size() && direBanCount != deque.size()) {
            Character c = deque.removeFirst();
            if (c == 'R') {
                if (direBanCount == 0) {
                    deque.addLast(c);
                    radiantBanCount++;
                } else {
                    direBanCount--;
                }
            } else {
                if (radiantBanCount == 0) {
                    deque.addLast(c);
                    direBanCount++;
                } else {
                    radiantBanCount--;
                }
            }
        }

        return (radiantBanCount > direBanCount) ? "Radiant" : "Dire";
    }
}