HackerRank [Bit Manipulation] Counter game /알고리즘 해커랭크

문제 주소 : www.hackerrank.com/challenges/counter-game/problem

 

문제 : Louise와 Richard가 번갈아 가며 주어진 숫자가 2의 제곱근 값인지 확인한다
2의 제곱근 값이라면 1/2 값을 상대에게 넘기고 아니라면 주어진 숫자보다 작은 숫자 중 가장 높은 2의 제곱 값과의 차이 값을 상대에게 넘겨주되 1을 넘겨주면 승리한다 Louise가 항상 먼저 시작한다

 

풀이 

1. 공학용 계산기에 2의 제곱근을 순서대로 입력해보았다 (2..4..8..16..32)
이 값들의 2진수 값들은 10, 100, 1000, 10000이다 가장 앞자리는 1이고 2의 승수만큼 뒤에 0이 붙는다
2. 전달받은 값 n을 2진수로 바꾸고 그 길이를 구한 뒤 그 길이와 같은 2의 제곱근 값을 따로 구한다
그 두 값을 비교하여 동일하면 나누기 2를 해서 상대 턴으로 넘기고 차이가난다면 차이값을 상대턴으로 넘긴다
3. 턴을 넘기기 전 n이 1이라면 게임을 종료시킨다

 

답안

#!/bin/python3

import math
import os
import random
import re
import sys
import math

# Complete the counterGame function below.
def counterGame(n):
    bLouise = False

    while True:
        bLouise = not(bLouise)
        nLen = len(bin(n))     
        sZero = '1'

        for i in range(nLen-3):
            sZero += '0' 

        sZero = '0b' +sZero     

        nTemp = int(sZero, 2)

        if n > nTemp:
            n -= nTemp
        elif n == nTemp:
            n = n//2
            
        if n == 1:
            if bLouise == True:
                return 'Louise'
            else:
                return 'Richard'           

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w') #vscode에서 돌리기위해 임시수정
    fptr = sys.stdout

    t = int(input())

    for t_itr in range(t):
        n = int(input())

        result = counterGame(n)

        fptr.write(result + '\n')

    fptr.close()

 

느낀 점

이번 문제도 문제 카테고리(비트 연산)가 없었다면 애먹었을 문제이다
처음엔 비트 연산이 여기서 어디서 쓰인다는 거지 하며 제곱근을 1씩 빼면서 근사값을 구했었는데
예제 2개를 제외하고 모두 타임아웃이 발생했다
그래도 푸는 감을 익혀놓으면 다음번 풀 때는 어렵지 않은 문제

---

틀린내용이나 질문은 댓글로 남겨주세요