[HackerRank] Chocolate in Box 풀이 - Kotlin

문제

HackerRank의 Chocolate in Box 문제는 게임 이론 문제다.

여러 개의 박스가 있고, 각 박스에는 초콜릿이 들어 있다.
두 명이 번갈아 가면서 게임을 한다.

한 번의 턴에는 다음 행동을 할 수 있다.

• 비어 있지 않은 박스 하나를 고른다.
• 그 박스에서 초콜릿을 1개 이상 가져간다.
• 더 이상 가져갈 초콜릿이 없는 사람이 진다.

Dexter가 먼저 시작할 때, 문제에서 구해야 하는 값은 다음과 같다.

Dexter가 첫 번째 수를 어떻게 두면, 이후 둘 다 최적으로 플레이했을 때 Dexter가 이길 수 있는지
그런 첫 번째 수의 개수

처음에는 모든 경우를 직접 세야 하나 싶었는데, 제한을 보면 그렇게 풀 수 없다.

1 ≤ N ≤ 10^6
1 ≤ A[i] ≤ 10^9

박스도 많고, 각 박스 안의 초콜릿 수도 크다.
그래서 모든 제거 경우를 시도하면 시간 초과가 난다.

---

핵심 아이디어

이 문제는 전형적인 Nim Game이다.

Nim Game은 여러 개의 더미가 있고, 한 턴에 하나의 더미에서 원하는 만큼 제거하는 게임이다.
이 문제에서는 초콜릿 박스가 더미 역할을 한다.

Nim Game의 중요한 규칙은 다음과 같다.

전체 XOR 값이 0이면 지는 상태
전체 XOR 값이 0이 아니면 이기는 상태

즉, 모든 박스의 초콜릿 개수를 XOR 했을 때 결과가 0이면 선공에게 불리하고,
0이 아니면 선공이 이길 수 있는 수가 있다.

Kotlin에서 XOR은 이렇게 쓴다.

a xor b

Python의 ^와 같은 역할이다.

---

예제 이해하기

예제 입력은 다음과 같다.

2
2 3

박스 상태는 다음과 같다.

[2, 3]

전체 XOR을 구하면 다음과 같다.

2 xor 3 = 1

전체 XOR이 0이 아니므로, Dexter는 이길 수 있는 수가 있다.

이제 어떤 박스를 줄이면 전체 XOR을 0으로 만들 수 있는지 확인하면 된다.

---

첫 번째 박스 확인

첫 번째 박스의 값은 2다.

target = 2 xor 1 = 3

즉, 첫 번째 박스를 3개로 만들면 전체 XOR이 0이 된다는 뜻이다.

하지만 초콜릿은 가져갈 수만 있고 늘릴 수는 없다.

2 → 3

이건 불가능하다.

---

두 번째 박스 확인

두 번째 박스의 값은 3이다.

target = 3 xor 1 = 2

3개짜리 박스를 2개로 줄일 수 있다.

[2, 3] → [2, 2]

이때 전체 XOR은 다음과 같다.

2 xor 2 = 0

상대에게 지는 상태를 넘겨줄 수 있으므로, 이 움직임은 Dexter가 이길 수 있는 첫 수다.

따라서 정답은 1이다.

---

공식

전체 XOR 값을 totalXor라고 하자.
현재 박스의 초콜릿 수를 chocolate이라고 하면, 이 박스를 줄였을 때 목표값은 다음과 같다.

val target = chocolate xor totalXor

이 target 값이 현재 초콜릿 수보다 작으면, 그 박스는 줄일 수 있다.

target < chocolate

그래서 이기는 첫 수의 개수는 다음 조건을 만족하는 박스의 개수다.

(chocolate xor totalXor) < chocolate

---

풀이 코드

fun chocolateInBox(arr: Array<Int>): Int {
    var totalXor = 0

    for (chocolate in arr) {
        totalXor = totalXor xor chocolate
    }

    if (totalXor == 0) {
        return 0
    }

    var answer = 0

    for (chocolate in arr) {
        val target = chocolate xor totalXor

        if (target < chocolate) {
            answer += 1
        }
    }

    return answer
}

---

코드 설명

먼저 전체 XOR 값을 구한다.

var totalXor = 0

for (chocolate in arr) {
    totalXor = totalXor xor chocolate
}

전체 XOR이 0이면 이미 선공이 불리한 상태다.
따라서 Dexter가 이기는 첫 수는 없다.

if (totalXor == 0) {
    return 0
}

전체 XOR이 0이 아니라면, 각 박스에 대해 줄일 수 있는지 확인한다.

for (chocolate in arr) {
    val target = chocolate xor totalXor

    if (target < chocolate) {
        answer += 1
    }
}

target < chocolate이면 그 박스를 target개로 줄일 수 있다는 뜻이다.
이렇게 줄이면 전체 XOR이 0이 되기 때문에 상대에게 불리한 상태를 넘길 수 있다.

---

Python 풀이와 비교

Python으로 쓰면 이런 느낌이다.

def chocolateInBox(arr):
    xor_sum = 0

    for x in arr:
        xor_sum ^= x

    if xor_sum == 0:
        return 0

    answer = 0

    for x in arr:
        if (x ^ xor_sum) < x:
            answer += 1

    return answer

Python에서는 ^를 쓰고, Kotlin에서는 xor를 쓴다는 차이만 기억하면 된다.

---

시간 복잡도

배열을 두 번 순회한다.

전체 XOR 계산: O(N)
가능한 첫 수 계산: O(N)

따라서 전체 시간 복잡도는 다음과 같다.

O(N)

추가로 큰 배열을 만들지 않기 때문에 공간 복잡도는 다음과 같다.

O(1)

---

정리

처음에는 게임 문제라서 어렵게 느껴졌는데, Nim Game이라는 걸 알면 풀이가 꽤 간단해진다.

핵심은 이거다.

전체 XOR이 0이면 지는 상태
전체 XOR이 0이 아니면 이기는 상태

그리고 Dexter가 이길 수 있는 첫 수의 개수는 다음 조건으로 구할 수 있다.

(chocolate xor totalXor) < chocolate

즉, 이 문제는 모든 경우를 직접 시도하는 문제가 아니라
XOR로 현재 게임 상태를 판단하는 문제였다.