[LeetCode] 649. Dota2 Senate

 

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

Dota2 Senate - LeetCode

문제 유형 : 그리디 / 큐 / 구현

문제 난이도 : Medium

 

문제

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

 

도타2에는 래디언트와 다이어라는 세력이 있다. 두 세력에서 온 의원들이 라운드제의 대결을 한다.

순서가 온 각 의원들은 두 가지 행동 중 하나를 할 수 있다:

• 다른 의원의 투표권 없애기 : 한 의원은 다른 의원의 투표권을 박탈시킬 수 있고, 다음 라운드에도 참여하지 못하게 한다.
• 승리 선언하기 : 다른 세력의 의원이 없을때, 승리를 선언할 수 있다.

의원들이 바보가 아니고, 자신이 소속한 세력을 위해 최선을 경우를 판단할 때, 어느 세력이 이기는지 구하시오.

 

 

입력

senate에 각 세력이 이니셜로 나열되어 총 n명이서 string 형태를 이루고 있다.

n == senate.length

1 <= n <= 10^4

senate[i]는 'R' 또는 'D'를 가진다.

 

ex) 'DDRRR'

 

출력

이기는 세력을 출력하시오

 

 

풀이

이기기 위해서는, 상대방이 없어야 한다. 서로 상대방의 투표권을 박탈시키고, 최종적으로 팀이 남아야 이긴다.

각 문자들의 배열을 만들어서 위치별로 인덱스를 넣어서, 인덱스끼리만 비교시키는 방법도 있지만, 나는 다른 방법으로 풀어 보았다.

입력받은 문자열을 큐에 넣고, 큐에서 나오는 의원이 투표권이 있으면 상대의 수를 줄이는 방식으로 했다.

그리고 이미 큐에 들어간 의원이 행동하지 못하게 skip변수를 만들어서, skip변수의 값이 1 이상이면 큐에서 나와도 아무것도 못하게 한다.

그 뒤, 공격한 의원은 다시 넣어 다음 라운드에 참가시키도록 했다.

 

 

코드(C++)

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<char> senates;
        int r_skip = 0;
        int d_skip = 0;
        int r_senates = 0;
        int d_senates = 0;

        for(int i = 0; i < senate.size(); i++){
            senates.push(senate[i]);
            if(senate[i] == 'R'){
                r_senates++;
            }
            else{
                d_senates++;
            }
        }

        while(!senates.empty()){
            char player = senates.front();
            senates.pop();
            if(player == 'R'){
                if(r_skip > 0){
                    r_skip--;
                    continue;
                }
                if(d_senates <= 0){
                    return "Radiant";
                }
                d_senates--;
                d_skip++;
                senates.push(player);
            }
            else{
                if(d_skip > 0){
                    d_skip--;
                    continue;
                }
                if(r_senates <= 0){
                    return "Dire";
                }
                r_senates--;
                r_skip++;
                senates.push(player);
            }
        }
        return r_senates <= 0 ? "Dire" : "Radiant";
    }
};