[LeetCode] 2038. Remove Colored Pieces if Both Neighbors are the Same Color

https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 그리디, 배열

문제 난이도 : Medium

 

문제

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.

 

한 줄에 n개의 조각들이 있다. 각 조각은 A 또는 B로 칠해져 있다.

Alice와 Bob은 번갈아가면서 조각을 지우는 게임을 하려고 한다. Alice부터 게임을 시작한다.

Alice는 A라고 칠해진 조각의 양 옆도 A인 경우에만 그 조각을 없앨 수 있다. B를 없애는 건 불가능하다.

Bob은 B라고 칠해진 조각의 양 옆도 B인 경우에만 그 조각을 없앨 수 있다. A를 없애는 건 불가능하다.

Alice와 Bob이 양 끝 타일을 없애는 건 불가능하다.

만약 자기 차례에 할 수 있는 행동이 없으면 패배한다.

 

Alice가 승리할 수 있다면 true를, 아니라면 false를 반환하시오.

 

풀이

1번 인덱스부터 n-1인덱스까지 단순하게 조건에 맞는 개수를 카운트해나가면 된다.

 

양 옆을 실제로 없애고 처음부터 구하는 작업은 필요 없다.

어차피 지우고도 계속 그 자리에서 조건에 만족하면, 굳이 없애지 않고도 그 다음의 인덱스 역시 조건을 만족한다는 뜻이다.

 

코드

C++

class Solution {
public:
    bool winnerOfGame(string colors) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int countA = 0;
        int countB = 0;
        const int n = colors.size();
        for (int i = 1; i < n - 1; i++) {
            if (colors[i-1] == 'A' && colors[i] == 'A' && colors[i + 1] == 'A') {
                countA++;
            }
            if (colors[i-1] == 'B' && colors[i] == 'B' && colors[i + 1] == 'B') {
                countB++;
            }
        }
        return countA > countB;
    }
};