[LeetCode] 2038. Remove Colored Pieces if Both Neighbors are the Same Color (C++)

Remove Colored Pieces if Both Neighbors are the Same Color - LeetCode

파이썬만 하다가 c++을 하려고 하다 보니 확실히 증감연산자(++,--)를 활용이 잘 안 되는 것 같습니다.

풀이

문제는 2개 이상의 연속된 A와 2개 이상의 연속된 B의 개수를 비교하면 쉽게 해결할 수 있었습니다.

• Alice와 Bob 모두 colors 배열 순서에 영향을 주지 못합니다.
• A는 A로 둘러쌓인, B는 B로 둘러싸인 것만 제거할 수 있습니다.

위와 같은 조건을 통해 결국 연속된 color가 많은 사람이 이기는 게임이라는 것을 알 수 있습니다.

 

Code

class Solution {
public:
    bool winnerOfGame(string colors) {
        int alice=0, bob=0, acount=0, bcount=0;
        for (char color : colors){
            if (color=='A'){
                bob = 0;
                if (++alice>2) {acount+=1;}
            }else{
                alice = 0;
                if (++bob>2) {bcount+=1;}
            }
        }
        return acount>bcount;
    }
};

아래 코드는 다른 사람들의 코드를 참고하여 c++를 다양하게 학습하고자 남겨 놓는 코드입니다.

class Solution {
public:
    bool winnerOfGame(string colors) {
        int alice = 0;
        int bob = 0;
        int prev = 0;
        int count = 0;
        colors.insert(colors.length(), 1, 'E');
        for (int color : colors){
            if (prev == color && color > 1){
                count += 1;
            }else{
                if (count>2 && prev=='A'){
                    alice += count-2;
                }else if (count>2 && prev=='B'){
                    bob += count-2;
                }
                count = 1;
                prev = color;
            }
        }
        if (alice>bob){
            return true;
        }else{
            return false;
        }
    }
};

풀이

There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the ith piece.

Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.

• Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
• Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
• Alice and Bob cannot remove pieces from the edge of the line.
• If a player cannot make a move on their turn, that player loses and the other player wins.

Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.

 

Example 1:

Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

Example 2:

Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

Example 3:

Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.

 

Constraints:

• 1 <= colors.length <= 105
• colors consists of only the letters 'A' and 'B'