Stone Game IX[Array,Math,Greedy,Counting,Game Theory]

https://leetcode.com/problems/stone-game-ix/description/

Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).

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

 

Example 1:

Input: stones = [2,1]
Output: true
Explanation: The game will be played as follows:
- Turn 1: Alice can remove either stone.
- Turn 2: Bob removes the remaining stone. 
The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.

Example 2:

Input: stones = [2]
Output: false
Explanation: Alice will remove the only stone, and the sum of the values on the removed stones is 2. 
Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.

Example 3:

Input: stones = [5,1,2,4,3]
Output: false
Explanation: Bob will always win. One possible way for Bob to win is shown below:
- Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1.
- Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4.
- Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8.
- Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10.
- Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15.
Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.

 

Constraints:

• 1 <= stones.length <= 105
• 1 <= stones[i] <= 104

아 코딩으로 Game좀 그만해라~~

 

1. Pyton

처음에 test case를 고려해서 요렇게 짜봤는데, 안 되는 경우가 있단다.

나는 경우의 수를 다 고려한 거 같은데 뭐가 안 된다는 거지..

 

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # 1) Sum of stones is not divisible by 3
        if sum(stones) % 3 != 0 : return False
        else:
            # 2) All stones are 3-divisible
            cond = True
            for x in stones:
                if x % 3 != 0:
                    cond = False
                    break
            if cond : return False

            # 3) len of List
            if len(stones) % 2 == 0 : return True
            else : return False

 

나는 이렇게 코드를 짰는데, 이러면 놓치는게 있다고 한다.

 

아직도 모르겠다..

 

일단 모범 답안은 아래와 같다.

 

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        count = [0, 0, 0]
        
        # 각 나머지 0, 1, 2로 돌을 그룹화하여 개수를 센다.
        for stone in stones:
            count[stone % 3] += 1
        
        # 나머지가 0인 돌의 개수가 짝수일 경우
        if count[0] % 2 == 0:
            # 나머지 1인 돌과 나머지 2인 돌이 모두 있는 경우 Alice가 이길 수 있다.
            return count[1] > 0 and count[2] > 0
        else:
            # 나머지가 0인 돌의 개수가 홀수일 경우
            # 나머지 1인 돌이 나머지 2인 돌보다 2개 이상 더 많거나,
            # 나머지 2인 돌이 나머지 1인 돌보다 2개 이상 더 많으면 Alice가 이길 수 있다.
            return abs(count[1] - count[2]) > 2

 

코드를 보고나니 이해가 간다만..

 

이런건 너무 수학문제다 코딩 문제락디보단 -_-

 

섭섭해서(?) C++로도 풀어보았다.

 

2. C++

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        vector<int> cnt(3,0);

        for(const int x : stones){
            cnt[x%3]++;
        }
        
        if(cnt[0]%2==0) return cnt[1] > 0 && cnt[2]>0;
        else return abs(cnt[1]-cnt[2]) >=3 ;
    }
};

코드 변환 수준의 문제풀이다. 에효!