C++로 풀어보는 칠판 XOR 게임 문제 완벽 가이드

문제 소개

칠판에 배열 nums의 원소들이 적혀 있다고 가정해 봅시다. 두 명의 플레이어인 램(Ram)과 샘(Sam)이 번갈아 가며 칠판에서 정확히 하나의 숫자를 지우는 게임을 진행합니다. 램이 먼저 시작합니다.

게임 규칙은 다음과 같습니다.

자신의 차례에 숫자를 지웠을 때, 칠판에 남아 있는 모든 원소의 비트 XOR 값이 0이 되면 그 플레이어가 패배합니다.
원소가 하나뿐일 때의 XOR 값은 그 원소 자신이며, 원소가 없을 때의 XOR 값은 0입니다.
만약 어떤 플레이어가 자신의 차례를 시작할 때 이미 칠판 전체의 XOR 값이 0이라면, 그 플레이어는 즉시 승리합니다.

예제로 이해하기

배열이 [1, 2, 1]이라고 해봅시다. 램은 1 또는 2를 지울 수 있습니다.

램이 먼저 1을 지우면 배열은 [2, 1]이 되고, XOR 값은 1 XOR 2 = 3입니다. 이후 샘이 아무 원소나 지워도 마지막 원소를 지우게 되는 사람은 램이므로 램이 지게 됩니다.
램이 먼저 2를 지우면 배열은 [1, 1]이 되고, XOR 값은 1 XOR 1 = 0이 됩니다. 따라서 램은 바로 패배하게 됩니다.

해결 접근 방법

이 문제는 게임 이론적 분석을 통해 간단한 조건으로 승패를 판단할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 배열의 모든 원소를 XOR한 값을 계산합니다.
초기 XOR 값이 0이면 첫 번째 플레이어(램)가 즉시 승리합니다.
배열의 크기(n)가 짝수이면 선공 플레이어가 항상 이길 수 있는 전략이 존재하고, 홀수이면서 초기 XOR이 0이 아니면 선공이 패배합니다.

알고리즘 단계

n := nums의 크기로 설정
x := 0으로 초기화
nums의 모든 원소 i에 대해 x := x XOR i 수행
x가 0이거나 n mod 2가 0이면 true 반환, 아니면 false 반환

C++ 구현 코드

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool xorGame(vector<int>& nums) {
      int n = nums.size();
      int x = 0;
      for(int i : nums) x ^= i;
      return x == 0 || n % 2 == 0;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1};
   cout << (ob.xorGame(v));
}

입력

{1,2,1}

출력

결과 분석

위 예제에서 입력 배열 {1, 2, 1}의 경우 전체 XOR 값은 0이 아니고(1 XOR 2 XOR 1 = 2), 배열의 크기 3은 홀수이므로 함수는 0(false)을 반환합니다. 즉, 램이 이 게임에서 승리할 방법이 없다는 의미입니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.