[LeetCode] 991. Broken Calculator - 문제풀이

Description

startValue 값을 가지고 있는 계산기에서 2를 곱하거나 1을 빼는 두가지 연산만 할 수 있을 경우 target이 될 수 있는 최소 연산 횟수를 반환하는 문제입니다.

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

• multiply the number on display by 2, or
• subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

Example 1:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Solution 1. Greedy

public int brokenCalc(int startValue, int target) {
    int cnt = 0;
    while(target > startValue){
        if(target % 2 == 0){
            target /= 2;
        }else{
            target++;
        }
        cnt++;
    }
    return cnt + (startValue - target);
}

반대로 생각하여 target을 기준으로 2로 나누거나 1을 더하는 연산을 하여 startValue에 접근해 나갑니다. 탐욕법을 이용해 2로 나누어 떨어질 때는 가장 나눠주고 그외에 케이스는 +1 연산을 해줍니다. target이 startvalue와 같거나 작아 졌을 경우 둘의 차이만큼만 startvalue에 -1 연산 횟수를 하면 동일해 지므로 startValue - target 만큼 cnt에 추가하여 반환해줍니다.

Reference

Broken Calculator - LeetCode