Leetcode 1927. Sum Game

문제

Alice and Bob take turns playing a game, with Alice starting first.

You are given a string num of even length consisting of digits and '?' characters. On each turn, a player will do the following if there is still at least one '?' in num:

Choose an index i where num[i] == '?'.
Replace num[i] with any digit between '0' and '9'.
The game ends when there are no more '?' characters in num.

For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal.

For example, if the game ended with num = "243801", then Bob wins because 2+4+3 = 8+0+1. If the game ended with num = "243803", then Alice wins because 2+4+3 != 8+0+3.
Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.

Alice와 Bob은 ?와 숫자로 이루어진 짝수 길이의 문자열 num을 가지고 게임을 한다.

Alice가 먼저 시작하며 자신의 차례에는 다음과 같이 행동한다.

1. num에서 ?인 위치 하나를 선택한다.
2. 해당 위치를 0부터 9까지의 숫자 중 하나로 변경한다.

모든 ?가 숫자로 변경되면 게임이 끝난다.

문자열을 정확히 절반으로 나누었을 때

• 왼쪽 절반의 숫자 합과 오른쪽 절반의 숫자 합이 같으면 Bob이 승리한다.
• 두 합이 다르면 Alice가 승리한다.

Alice와 Bob이 모두 최선의 방법으로 플레이한다고 할 때 Alice가 승리한다면 true, Bob이 승리한다면 false를 반환한다.

---

예시

Input: num = "5023"
Output: false

문자열을 절반으로 나누면

50 | 23

이다.

왼쪽의 합은

오른쪽의 합은

이다.

이미 모든 숫자가 결정되어 있고 두 합이 같기 때문에 Bob이 승리한다.

---

제한

• $2 \le num.length \le 10^5$
• num.length는 짝수이다.
• num은 숫자와 ?로만 이루어져 있다.

---

풀이

우선 문자열을 절반으로 나누고 다음 네 가지 값을 구한다.

L   # 왼쪽에 이미 존재하는 숫자의 합
R   # 오른쪽에 이미 존재하는 숫자의 합

Lq  # 왼쪽 ?의 개수
Rq  # 오른쪽 ?의 개수

이 문제에서 Alice는 두 합을 다르게 만들려고 하고 Bob은 두 합을 정확하게 같게 만들려고 한다.

따라서 Bob이 이길 수 있는 상황을 찾는 것이 더 쉽다.

Bob이 ? 두 개를 처리하는 방법

같은 쪽에 ?가 두 개 남아 있다고 생각해보자.

Alice가 첫 번째 ?에 x를 넣었다면 Bob은 다른 ?에

를 넣을 수 있다.

예를 들어 Alice가 7을 넣으면 Bob은 2를 넣는다.

7 + 2 = 9

Alice가 3을 넣으면 Bob은 6을 넣는다.

3 + 6 = 9

Alice가 0을 넣어도 Bob은 9를 넣을 수 있다.

0 + 9 = 9

즉 Alice가 어떤 숫자를 선택하더라도

로 만들 수 있다.

9인 이유는 숫자로 사용할 수 있는 범위가 0부터 9까지이기 때문이다.

예를 들어 합을 7로 고정하려고 하면 Alice가 9를 선택했을 때 Bob은 -2를 선택해야 한다.

반대로 합을 10으로 고정하려고 하면 Alice가 0을 선택했을 때 Bob은 10을 선택해야 한다.

둘 다 사용할 수 없는 숫자이다.

하지만 합이 9라면

Alice 0 → Bob 9
Alice 1 → Bob 8
Alice 2 → Bob 7
...
Alice 8 → Bob 1
Alice 9 → Bob 0

와 같이 Alice의 모든 선택에 대응할 수 있다.

따라서 같은 쪽에 있는 ? 두 개는 게임상

의 가치를 가진다고 생각할 수 있다.

그러면 ? 하나의 평균적인 가치는

가 된다.

---

반대쪽에 존재하는 ?

이번에는 다음과 같이 양쪽에 ?가 하나씩 있다고 생각해보자.

?5 | 5?

Alice가 왼쪽에 7을 넣는다면

75 | 5?

Bob은 오른쪽에 똑같이 7을 넣으면 된다.

75 | 57

그러면

이므로 Alice가 추가한 값의 영향을 그대로 상쇄할 수 있다.

따라서 왼쪽과 오른쪽의 ?는 하나씩 서로 제거해서 생각할 수 있다.

결국 중요한 것은

즉 양쪽 ? 개수의 차이이다.

---

1923????으로 생각해보기

문자열이 다음과 같다고 해보자.

1923 | ????

현재 왼쪽의 합은

이다.

오른쪽에는 ?가 네 개 있다.

? 두 개마다 Alice와 Bob이 한 번씩 선택하게 되고 Bob이 Alice에게 완벽하게 대응할 수 있다면 두 칸의 합은 9가 된다.

따라서 네 칸의 기준값은

이다.

하지만 왼쪽의 합은 15이다.

왼쪽  = 15
오른쪽 = 18

Bob이 자신의 대응 전략으로 만들어낼 수 있는 균형점과 실제 필요한 값이 다르다.

따라서 Alice가 이길 수 있다.

반대로

18 | ??

라면 왼쪽의 합은 9이고 오른쪽 ? 두 개 역시 Bob이 9로 만들 수 있기 때문에 Bob이 이길 수 있다.

---

Bob의 승리 조건

? 하나를 4.5의 가치로 생각하면 Bob이 이기기 위해서는

가 되어야 한다.

식을 정리하면

이고

이므로

가 된다.

소수점 계산을 하지 않기 위해 양변에 2를 곱하면

가 된다.

이 조건이 정확하게 성립할 때만 Bob이 승리한다.

따라서 Alice의 승리 조건은

(L - R) * 2 != (Rq - Lq) * 9

이다.

---

?가 홀수인 경우

따로 처리할 필요도 없다.

전체 ?의 개수가 홀수라면 Rq - Lq 역시 홀수이다.

따라서

는 홀수가 된다.

반면

는 항상 짝수이다.

짝수와 홀수는 같을 수 없기 때문에

가 자동으로 성립한다.

즉 Alice가 마지막 ?를 선택하게 되는 경우까지 하나의 식으로 처리할 수 있다.

---

코드

class Solution:
    def sumGame(self, num: str) -> bool:
        L, R = 0, 0
        Lq, Rq = 0, 0
        N = len(num)

        for i, v in enumerate(num):
            if i < N // 2:
                if v == '?':
                    Lq += 1
                else:
                    L += int(v)
            else:
                if v == '?':
                    Rq += 1
                else:
                    R += int(v)

        return (L - R) * 2 != (Rq - Lq) * 9

문자열을 한 번 순회하기 때문에 시간 복잡도는

이고 별도의 배열을 사용하지 않기 때문에 공간 복잡도는

이다.