Dota2 Senate

문제설명

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

제한사항

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

입출력 예

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.

답

내가 쓴 답

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function(senate) {
    let arr = senate.split("")
    let arrR = arr.filter(element => element === "R").length
    let arrD = arr.filter(element => element === "D").length
    
    if(arrR>arrD) {
        return "Radiant"
    }
    else if (arrR === arrD) {
        if(arr[0]==="R") {
            return "Radiant"
        }
        else if(arr[0] === "D") {
            return "Dire"
        }
    }
    else if(arrR<arrD) {
        return "Dire"
    }
};

70 / 82 testcases passed
이 코드가 틀렸던 이유는

senate ="DDRRR" 의 경우에 대해서 알 수 있다.

나는 이 문제를 풀었을때 박탈 과정을 단순히 radiant와 dire중에 어느 표가 많이 나왔는지로 생각하면 된다고 문제를 생각했는데, 박탈 과정의 핵심은 배열내에서 가장 먼저 오는게 핵심인 개념이었다.

수정한 답

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function(senate) {
    let queueR = [];
    let queueD = [];
    
    for (let i = 0; i < senate.length; i++) {
        if (senate[i] === "R") {
            queueR.push(i);
        } else {
            queueD.push(i);
        }
    }
    
    while (queueR.length > 0 && queueD.length > 0) {
        if (queueR[0] < queueD[0]) {
            queueR.push(queueR[0] + senate.length);
        } else {
            queueD.push(queueD[0] + senate.length);
        }
        
        queueR.shift();
        queueD.shift();
    }
    
    return queueR.length > 0 ? "Radiant" : "Dire";
};

다른풀이

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function(senate) {
    //initialize an array to act as a stack
    //split the senate string into an array
    //loop through senate
        //if the stack is empty, push in the senator
        //if the top of the stack is equal to the senator, push in the senator
        //if the top of the stack is not equal to the senator
            //push the senator at the top of the stack back into the senateArray
    //the last member in the stack will declare the winner
    const stack = [];
    const senateArray = senate.split('');
    for (let i = 0; i < senateArray.length; i++) {
        if (!stack.length) {
            stack.push(senateArray[i]);
        } else if (stack.length && stack[stack.length - 1] === senateArray[i]) {
            stack.push(senateArray[i]);
        } else {
            senateArray.push(stack.pop());
        }
    }
    return stack[0] === 'R' ? 'Radiant' : 'Dire';
};

속도 백분위

피드백

1. 큐라는 것을 캐치하지 못했다.
   큐에 대한 내용이 좀 더 확실히 머릿속에 잡혀 있었다면 문제의 규칙을 찾아내는 과정에서 큐의 개념을 떠올렸을텐데, 아쉽다.

• 규칙을 한정적으로 이해하지 않도록하자.

2. 버그는 미연에 방지해야하는 것이다.

이 문제를 풀때, i번째 인덱스가 i+1번째 인덱스와 같지 않은경우 splice(i+1, 1, "")을 통해 i+1 인덱스를 ""로 만든후, ""를 join("").split("")로 공백을 지워가는 식으로 while문을 돌려서 문제를 풀려고 했지만, 이는 잘못된 알고리즘이었다.
왜냐하면 "RRDDD"인 경우 0번째와 1번째가 같으니 D에게 발휘했어야할 효력을 전혀 발휘하지 않고 그냥 넘어가게 된다. 이렇게 된다면 첫번째 사이클에서 RR__D가 되어야할 결과가 RR_DD로 된다.

이번 문제를 통해서 배우게 된 것은 알고리즘 아이디어가 떠올랐다고 바로 실행에 옮겨 알고리즘을 짜기보다 그 아이디어가 논리적으로 옳은지 검증부터 해야한다.
다시말해, 알고리즘을 짜기위해 문제를 해석해낸 관점이 올바른 관점인지 논리적으로 옳은지 아닌지 알고리즘을 짜기전, 테스트 케이스를 떠올려 확인해야한다.

지금 이 경우에 내가 제시한 관점은 i번째 인덱스가 i+1번째 인덱스와 같지 않은경우 공백으로 덮어씌우는 알고리즘이었다. 이 관점부터 먼저 점검해야한다.

복습

1. Filter()함수
filter() 함수는 배열에서 특정 조건을 만족하는 요소들만 추출하여 새로운 배열을 생성한다.

2. 화살표 함수

(parameters) => expression

parameters: 함수의 인자들을 정의한다. 인자가 하나뿐이라면, 괄호를 생략할 수 있다.

expression: 함수의 본문이다. 중괄호 {}를 사용하지 않으면, 이 표현식의 결과값이 자동으로 반환된다.
만약 함수의 본문에 여러 문장이 필요하다면, 중괄호를 사용하여 함수 본문을 작성하고, return 키워드로 값을 반환해야 한다.