649. Dota2 Senate

Dota2 Senate - LeetCode

 

도타2 세네이트에는 Radiant와 Dire 두 파티의 선거인이 있습니다. 이제 세네이트는 도타2 게임의 변경 사항을 결정하려고 합니다. 이 변경 사항에 대한 투표는 라운드 기반 절차입니다. 각 라운드에서 각 선거인은 두 가지 권리 중 하나를 행사할 수 있습니다.
선거인의 권리 중 하나를 박탈:선거인은 다른 선거인의 모든 권리를 이번 및 이후의 모든 라운드에서 상실하도록 할 수 있습니다.
승리 선언: 만약 이 선거인이 투표 권리를 가진 선거인이 모두 동일한 파티에서 나왔다면, 그는 승리를 선언하고 게임의 변경을 결정할 수 있습니다.

각 선거인의 파티 소속을 나타내는 문자열 senate가 주어집니다. 'R'과 'D'는 각각 Radiant 파티와 Dire 파티를 나타냅니다. 그런 다음 선거인이 n 명인 경우 주어진 문자열의 크기는 n입니다.
라운드 기반 절차는 주어진 순서대로 첫 번째 선거인에서 마지막 선거인까지 진행됩니다. 이 절차는 투표가 종료될 때까지 계속됩니다. 권리를 상실한 선거인은 절차 중에 무시됩니다.
모든 선거인이 충분히 똑똑하고 자신의 파티를 위한 최상의 전략을 사용할 것으로 가정합니다. 최종적으로 승리를 선언하고 도타2 게임을 변경할 파티를 예측하세요. 출력은 "Radiant" 또는 "Dire"여야 합니다.

 

 

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".

 

Example 1:

Input: senate = "RD"
Output: "Radiant"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: senate = "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in round 1. 
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

 

풀이과정 설명:

Queue를 사용하여 Radiant와 Dire의 선거인을 각각 저장합니다.
각 선거인의 인덱스를 큐에 저장하면서 Radiant는 양수, Dire는 음수로 구분합니다.
두 큐 중 하나라도 비어 있지 않은 동안에 반복문을 실행하면서 라운드를 시뮬레이션합니다.
현재 라운드에서 가장 먼저 투표하는 선거인을 가져와서 다음 라운드에 추가합니다.
마지막에 승리를 선언할 파티를 반환합니다.

class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> queR = new LinkedList<>();
        Queue<Integer> queD = new LinkedList<>();

        String[] arrStr = senate.split("");
        int strLen = arrStr.length;

        for (int i = 0; i < strLen; i++) {
            if (arrStr[i].equals("R")) {
                queR.offer(i);
            } else {
                queD.offer(i);
            }
        }

        while (!queR.isEmpty() && !queD.isEmpty()) {
            if(queR.peek() > queD.peek()){
                queR.poll();
                queD.offer(queD.poll() + strLen);
            }else{
                queD.poll();
                queR.offer(queR.poll() + strLen);
            }
        }

        return queD.isEmpty() ? "Radiant" : "Dire";
    }
}