Leetcode Daily Challenge - 깨진 계산기

수학/욕심 문제를 기반으로 하는 Leetcode에 대한 오늘의 도전 과제입니다. 중간 수준의 문제이고 쉽게 들리지만 최적의 솔루션 측면에서 머리를 긁적일 수 있습니다.

991. Broken Calculator


문제 설명

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

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

사고 과정:

즉시 떠오르는 생각은 * 연산자를 사용하여 startValue를 늘리거나(startValue가 더 작은 경우) 이를 빼서 감소시켜 목표와 동일하게 만들고 여정에서 취한 단계를 계산하는 것입니다.

오류가 발생할 수 있으므로 원하는 방법은 역방향 접근 방식을 수행하는 것입니다. 나눗셈과 뺄셈의 정반대 연산자를 사용하여 대상을 축소하여 연산 발생 횟수를 계산합니다.

target이 startValue보다 작은 경우 startValue까지 증가하고 실제 카운터와 함께 그 차이를 반환합니다. 이 단계에 대해 혼란스러워서 더 진행하고 이해하십시오.

논리

접근 방식은 간단합니다. 카운터를 선언하고 대상 값이 startValue보다 크지 않으면 종료되는 루프를 실행합니다.

목표가 홀수인 경우 목표 값을 1씩 증가시키고 그렇지 않으면 목표 값을 반으로 나눕니다.

결국 루프가 종료되면 루프가 실행된 총 횟수와 startValue와 대상 간의 차이를 반환합니다.

루프를 따라 실행된 카운터와 함께 대상과 동일하게 만들기 위해 startValue의 다른 쪽에서 startValue와 대상 간의 차이가 감소합니다.

암호

Python 연습을 처음부터 배우고 싶거나 DSA를 연습하고 싶다면 내 YouTube 채널에서 무료 강의 및 코드 따라 세션을 확인하세요!