[LeetCode] Broken Calculator

https://leetcode.com/problems/broken-calculator/

Broken Calculator - LeetCode

자꾸 풀라고 알람이 와서 풀어버리겠다!!

2를 곱하거나 1을 빼거나 해서 최소 횟수로 target 만들기

첫 풀이

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        q : Deque = collections.deque()
        q.append((startValue, 0))
        while q:
            now, count = q.popleft()
            if now == target:
                return count
            else:
                if now < target:
                    q.append((now*2, count+1))
                if now-1 > 0:
                    q.append((now-1, count+1))

처음엔 최소? BFS? 라고 생각하고 풀었는데, 이렇게 BFS로 풀면 메모리 이슈가 있다.

 

비트 연산 풀이

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        if startValue >= target:
            return startValue-target
        count = 0
        while target > startValue:
            # 2 나머지 있을 때
            if target & 1:
                target += 1
                count += 1
            target >>= 1
            count += 1
        count += startValue-target
        return count