Problem

1. input: 정수 dividend, divisor
2. output: dividend를 divisor로 나누었을 때 몫 리턴
3. 소수점은 버림
4. int의 범위를 벗어나는 경우 해당 끝 값 리턴
5. 나누기, 곱하기, 나머지 연산 사용 금지
   • 2^31 <= dividend, divisor <= 2^31 - 1
   • divisor != 0

Idea

나누기, 곱셈 연산을 사용할 수 없으므로 dividend에서 divisor을 계속해서 빼주면서 몫을 구하려고 하면 당연히 시간초과가 날 것이다 → Sol1

다른 연산이 불가능하므로 divisor를 계속해서 빼주는 것은 맞을 것이다, 즉 매번 divisor를 빼주는 부분을 발전시켜야 한다.

divisor를 누적해서 빼주면 연산횟수를 n번에서 log n 으로 줄일 수 있다 → Sol2

⇒ 하지만 해당 과정에서 Long을 사용하기 때문에 반쪽짜리 답.. (Long을 사용하지 않고 풀이가 가능한가..)

Solution

1. • divisor

   dividend - divisor 반복

   class Solution {
       fun divide(dividend: Int, divisor: Int): Int {
           if (dividend == Int.MIN_VALUE && divisor == -1) return Int.MAX_VALUE
           var tmp = 0
           var cnt = 0
           while (tmp <= Math.abs(dividend)) {
               tmp += Math.abs(divisor)
               cnt++
           }
           if (dividend < 0 && divisor > 0) {
               return -cnt+1
           } else if (dividend > 0 && divisor < 0) {
               return -cnt+1
           } else {
               return cnt-1
           }
       }
   }
   

   시간 복잡도: dividend / divisor = n

   ⇒ 시간 초과

2. • divisor 배수

   • divisor를 배수로 뺄셈 반복

   class Solution {
       fun divide(dividend: Int, divisor: Int): Int {
           // - 경계값 처리
           if (dividend == Int.MIN_VALUE && divisor == -1) return Int.MAX_VALUE
           // 1이나 -1로 나누는 경우 처리
           if ((divisor == 1 && dividend > 0) || (divisor == -1 && dividend < 0)) return Math.abs(dividend)
           if ((divisor == -1 && dividend < 0) || (divisor == 1 && dividend < 0)) return -Math.abs(dividend)
   
           val num1 = Math.abs(dividend.toLong())
           val num2 = Math.abs(divisor.toLong())
           if (num1 < num2) return 0
   
           return if ((dividend < 0 && divisor < 0) || (dividend > 0 && divisor > 0)) doubleDivide(num1, num2)
           else -doubleDivide(num1, num2)
       }
   
       fun doubleDivide(dividend: Long, divisor: Long): Int {
           var doubled = divisor
           var times = 1
   
           while (dividend - doubled - doubled >= 0) {// 다음 뺄셈이 안되는 경우 break
               times += times // 배수
               doubled += doubled // 빼는 값
           }
   
           return if (dividend - doubled < divisor) times // 뺄셈 불가능 && 남은 값 divisor보다 작음
           else times + doubleDivide(dividend - doubled, divisor) // 뺄셈 불가능 but 남은 값 divisor 보다 큼
       }
   }
   

   시간 복잡도: log n

   

Point

1. 나누기 연산 없이 나눗셈 하는 방법 ⇒ 뺄셈의 반복 ⇒ 배수로 뺄셈