[LeetCode] 464. Can I Win

😎풀이

1. 뽑은 카드를 Set 혹은 Array로 관리하는 것이 아닌, 특정 비트 마스크(정수)로 관리하여 Key 형태로 변환하는 과정 최적화
2. DFS 형태로 뽑을 수 있는 카드를 한장씩 뽑으며, 게임 결과를 맵핑하여 최적화
3. 게임 승리 조건은 다음과 같음
   3-1. 내 차례에 특정 카드로 목표치와 동일하거나 초과한 수를 만들 수 있음
   3-2. 상대방의 차례에 이 게임을 승리하지 못함
4. 내 승패 여부를 반환

function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
    const sum = Math.floor((maxChoosableInteger * (maxChoosableInteger + 1)) / 2)
    if(sum < desiredTotal) return false
    const resultMap = new Map<number, boolean>()
    function isWin(bitMask: number, remainTotal: number) {
        if(resultMap.has(bitMask)) return resultMap.get(bitMask)
        for(let i = 1; i <= maxChoosableInteger; i++) {
            const bit = 1 << (i - 1)
            if(bitMask & bit) continue
            if(remainTotal - i <= 0 || !isWin((bitMask | bit), remainTotal - i)) {
                resultMap.set(bitMask, true)
                return true
            }
        }
        resultMap.set(bitMask, false)
        return false
    }
    return isWin(0, desiredTotal)
};