LeetCode Q - Broken Calculator ( Java )

February LeetCoding Challenge 2021 ( Week 3, day 21 )

Q : Broken Calculator

 

---

문제 해설

 

계산기가 고장나 곱하기 2 와 빼기 1 밖에 되지 않는다.

화면에 표시되는 숫자 X를 Y로 바꾸기 위한 최소한의 계산 횟수를 반환하라. 

 

 

---

문제 풀이

거꾸로 풀자.

 

• 2로 나누기 를 작업 1 이라 하고
• 1 더하기 를 작업 2 라고 하자

 

1. Y 값을 X 값보다 작아질때까지 2로 나눈다. (작업 1)

• 2로 나누다가 Y값이 홀수가 된다면 +1 (작업 2)
• 작업 1 과 작업 2 의 횟수를 기록

2. Y 값이 X 값보다 작아지면 작업 1 과 작업 2의 횟수에 X - Y 값을 더해 반환

•  작아진 Y 값을 X 값과 같게 하려면 작업 2 를 X - Y 번 해야하므로..

 

 

class Solution {
    public int brokenCalc(int X, int Y) {
      int ans = 0;
      while (Y > X) {
        if ( Y % 2 == 1 ) {
          Y += 1;
        }
        else {
          Y = Y / 2;
        }
        ans++;
      }
      return ans + X - Y;
    }
}

 

 

Runtime : 0 ms , beats 100.00% of java submissions

Memory usage : 35.5 MB, beats 92.13% of java submission

 

 

 

좋은 결과가 나온다.

---

 

결 론

 

 

정석대로 풀려면 어렵고 복잡한 문제가 있을때는 거꾸로 푸는 방식이 더 좋은 경우가 있으므로 거꾸로 푸는것도 생각해보자.