[LeetCode] Dota2 Senate

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

 

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.


Constraints:
n == senate.length
1 <= n <= 104
senate[i] is either 'R' or 'D'.

---

Dota2라는 게임에 평의회가 나온다...는군.

 

롤같은 게임인가베

 

두 개의 진영에서 각각 의원??들이 존재한다.
이 의원들은 전세를 뒤엎을 수 있는 투표를 진행하고, 라운드 방식으로 진행이 된다.
라운드마다 각 의원들은 두 개의 권리 중 하나를 실행할 수 있다.
1. 한 명의 의원의 권리를 박탈하기 -> 이후 라운드에도 적용됨
2. 승리를 선언 -> 같은 진영에 있는 의원들이 아직 권리를 실행할 수 있다면, 승리를 선언할 수 있음
senate라는 문자열이 주어지고, 이 문자열은 의원들의 진영을 나타낸다. (R은 Radiant, D는 Dire)
n명의 의원들이 있는 경우 문자열의 길이도 n이다.
각 라운드는 첫 의원부터 마지막 의원까지 주어진 순서대로 진행되고, 마지막 투표까지 유지된다.
권리를 잃은 모든 의원의 순서는 라운드 동안 스킵된다.
모든 의원이 충분히 똑똑하고 항상 자신의 진영에 있어 최선의 전략을 사용한다고 가정한다.
어떤 진영이 마지막에 승리를 선언하고 전세를 엎을 수 있는지 예측해라. -> Radiant, Dire 둘 중 하나를 리턴

 

const predictPartyVictory = function(senate) {
    // 앞에서부터 뒤에 반대 진영이 있으면 그 진영을 빼고 푸시한다.
    const temp = [];
    for(let i=0; i < senate.length; i++){
        if(senate[i+1]){
            if(senate[i] == senate[i+1]){
                temp.push(senate[i]);
                temp.push(senate[i+1]);
            }else{
                temp.push(senate[i]);
            }
        }else{
            if(senate[0] == senate[i]){
                temp.push(senate[i]);
            }else{
                temp.push(senate[i]);
                temp.shift();
            }
        }
        i ++;
    }
    // 한 바퀴 돌고 나면 숫자가 더 많은 쪽이 이긴다.
    let R = 0;
    let D = 0;
    let first = temp[0];
    for(let j=0; j<temp.length; j++){
        if(temp[j] === 'R'){
            R++;
        }else{
            D++;
        }
    }

    // 숫자가 동일하면 먼저 시작하는 쪽이 이긴다.
    if(R === D){
        return first === "R" ? "Radiant" : "Dire";
    }else if(R < D){
        return "Dire";
    }else{
        return "Radiant";
    }
};

이렇게 하니까 테스트케이스 83개중에 66개는 통과했는데ㅋㅋㅋ

67번째 테스트케이스인 "DDRRR"을 통과하지 못했다.

바로 뒤 의원이 아니라 그냥 자기 뒤에 있는 의원이기만 하면 권리를 박탈할 수 있어서...

 

큐(Queue)는 선입선출 개념으로, 줄서기와 비슷하다.

그걸 이용해서 풀면... 

const predictPartyVictory = function(senate) {
    // 한 진영밖에 없으면 그냥 Set으로 판별
    const distinct = new Set([...senate]);
    if(distinct.size === 1){
        if(distinct.has("D")){
            return "Dire";
        }else{
            return "Radiant";
        }
    }
    let dire = [];
    let radiant = [];
    for(let i=0; i<senate.length; i++){
        if(senate[i] === "R"){
            radiant.push(i);
        }else{
            dire.push(i);
        }
    }
    let delay = senate.length;
    while(dire.length && radiant.length){
        const r = radiant.shift();
        const d = dire.shift();

        // 다시 맨 뒤로 가서 줄서기
        if(r < d){
            radiant.push(r + delay);
        }else{
            dire.push(d + delay);
        }
    }

    return dire.length ? "Dire" : "Radiant";
};

이렇게 할 수 있다...

그냥 맨 앞에서부터 각 진영의 인덱스를 넣은 큐를 각각 만들고

맨 앞에서부터 각각 숫자를 비교해서 더 앞에 있는 사람을 다시 각 진영의 맨 뒤로 보낸다.

그리고 이렇게 한 쪽 진영의 길이가 0이 될 때까지 while 반복문을 돈다.

 

막상 해답이 나오면 별 거 아닌데 여기까지 깨닫는게 쉽지가 않다ㅋㅋㅋ

 

그리고 또 혹시나 해서 훔쳐온 1등 코드.. (주석 추가함)

var predictPartyVictory = function(senate) {
  let queue = senate.split(''); // queue up
  let count = 0, i = 0; // -/+ ~ R/D

  while (i < queue.length) {
    let curr = queue[i];

    if (curr === 'R') {
      if (count > 0) {
        // D가 우세한 경우 → R이 금지될 차례, D 하나 추가
        queue.push('D');
      }
      count--; // R 등장 → R 쪽에 기울기
    } else {
      if (count < 0) {
        // R이 우세한 경우 → D가 금지될 차례, R 하나 추가
        queue.push('R');
      }
      count++; // D 등장 → D 쪽에 기울기
    }

    i++;
  }

  return (count < 0) ? 'Radiant' : 'Dire';
};

 

이건 사람이 아니라 컴퓨터 아닌가?ㅋㅋㅋㅋㅋ 어떻게 이런 생각을 해내는지 신기할 따름...

범인은 욕심부리지 말고 범인답게 풀어야지...^_^