LeetCode 29(Divide Two Integers, Python)

1. 문제 링크

• LeetCode - The World's Leading Online Programming Learning Platform

Divide Two Integers - LeetCode

2. 문제 설명

• 정수의 나눗셈 후 소수부분을 절사하여 정수 부분을 반환
• 하지만 multiplication, division, mod 연산 사용하지 않기
• 2^31-1 보다 크면 2^31-1을, -2^31보다 작으면 -2^31을 반환
• 예시1) 10을 3으로 나누면 3.333 이므로 3 반환
• 예시2) 7을 -3으로 나누면 -2.333 이므로 -2 반환

3. 처음 풀이

• 29ms(97.92%), 16.5mb(12.76)
• 우선 -2.333 이 -2가 되는 것은 2.333을 2로 바꾼 후 부호만 처리하면 됨을 알 수 있음. 따라서 그냥 양수로 바꾸어 몫을 구한 후 부호를 생각하면 됨.
• 10을 3으로 나누는 경우를 생각해보자. 몫은 3이 10 안에 몇 번 들어가는 지를 나타내는 값으로 10 나누기 3의 몫이 3인 이유는 3이 3번 (3*3=9)가 10에 들어가고 그 다음에는 3이 못 들어가기 때문
• 따라서 10에서 3을 3번까지 빼면 0이상이고, 4번 빼면 음수임을 알 수 있음.
• 그래서 그냥 반복해서 3을 한번씩 빼며 부호가 바뀌는 지점까지 뺄셈 횟수를 카운트하였다. 이 경우 time limit error 발생
• 그래서 3을 한번씩 빼지말고 좀 더 크게 크게 빼주어야한다고 판단, 하지만 곱셈 연산을 쓰지 못하므로 덧셈을 두번하여 더블링을 반복하여 빼주었음.
• 예를 들어 34를 3으로 나누는 상황을 생각하면
  • 34-3=31 → 뺄셈 횟수 1
  • 31-6=25(6=3+3) → 뺄셈 횟수 1+2
  • 25-12=13(12=6+6) → 뺄셈 횟수 1+2+4
  • 13-24=-11(24=12+12) → 뺄셈 횟수 1+2+4+8
  • 이제 음수가 되었으므로 다시 3을 더하기 시작함
  • -11+3=-8 → 뺄셈 횟수 1+2+4+8-1
  • -8+6=-2(6=3+3) → 뺄셈 횟수 1+2+4+8-1-2
  • -2+12=10(12=6+6) → 뺄셈 횟수 1+2+4+8-1-2-4
  • 다시 양수이므로 3을 빼기 시작함
  • 10-3=7 → 뺄셈 횟수 1+2+4+8-1-2-4+1
  • 7-6=1(3+3=6) → 뺄셈 횟수 1+2+4+8-1-2-4+1+2 = 11
  • 이제 1은 0이상 3미만이 되었으므로 멈추고 3을 11번 뺀 것이므로 답은 11

  class Solution:
      def divide(self, dividend: int, divisor: int) -> int:
          if dividend == 0:
              return 0
          if divisor == 1:
              if dividend >= 2147483647:
                  return 2147483647
              elif dividend <-2147483648:
                  return -2147483648
              else:
                  return dividend
          
  
          def positive(a,b):
              c = b
              time = 0
              while True:
                  cnt = 1 
                  c = b
                  if 0 <= a and a < b:
                      return time
                  elif a >= b:
                      while a >= b:
                          a -= c
                          c += c
                          cnt += cnt
                      time += (cnt-1)
                  elif a < 0:
                      while a < 0:
                          a += c
                          c += c
                          cnt += cnt
                      time -= (cnt-1)
                  
          if dividend > 0 and divisor > 0:
              result = positive(dividend, divisor)
          elif dividend < 0 and divisor <0:
              result = positive(-dividend, -divisor)
          elif dividend <0:
              result = -positive(-dividend, divisor)
          else:
              result = -positive(dividend,-divisor)
  
          if result >= 2147483647:
              return 2147483647
          elif result <-2147483648:
              return -2147483648
          else:
              return result

4. 다음 풀이

• 핵심 로직은 동일하지만 코드 가독성이 훨씬 높다.

class Solution:
    def divide(self, dividend, divisor):
        # 부호가 같으면 양수, 다르면 음수
        positive = (dividend < 0) is (divisor < 0)
        
        # 나눠지는 수와 나누는 수의 절댓값 사용
        dividend, divisor = abs(dividend), abs(divisor)
        
        # 결과 변수 초기화
        res = 0
        
        # 나누는 수가 나눠지는 수보다 크거나 같을 때까지 반복
        while dividend >= divisor:
            curr_divisor, num_divisors = divisor, 1
            
            # 현재 나누는 수가 나눠지는 수보다 크거나 같을 때까지 반복
            while dividend >= curr_divisor:
                dividend -= curr_divisor
                res += num_divisors
                
                # 현재 나누는 수를 왼쪽 시프트하여 두 배로 증가
                curr_divisor = curr_divisor << 1
                num_divisors = num_divisors << 1
                
        # 결과가 음수인 경우 부호 변경
        if not positive:
            res = -res
        
        # 결과가 32비트 부호 있는 정수 범위 내에 있도록 조정
        return min(max(-2147483648, res), 2147483647)

 

---

• 와 이 풀이 미쳤다.
• range의 특성 이용. range를 이렇게 쓸 수가 있어!!!!!!
• range(0, 32, 3)이라고 하면 0이상 32미만에서 3씩 커지면서 나오니까
  • 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30으로 총 10개가 나오는데 이게 바로 31을 3으로 나눈 몫이다.
• 반복문의 속도
  • range의 경우 C언어로 처리되고 끝이다. while문으로 작성할 경우 그 안의 내용을 파이썬이 처리한다. 당연히 모든 것을 C언어로 처리하는 range 풀이가 더 빠름.

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = -1 if (dividend >= 0 and divisor < 0) or (dividend < 0 and divisor >= 0) else 1
        dividend = abs(dividend)
        divisor = abs(divisor)
        result = len(range(0, dividend-divisor+1, divisor))
        if sign == -1:
            result = -result
        minus_limit = -(2**31)
        plus_limit = (2**31 - 1)
        result = min(max(result, minus_limit), plus_limit)
        return result

---

• 비트 연산을 이용한 풀이
• range 풀이 말고 연산을 이용한 풀이 중에서 가장 간결한 논리.
• dividend=34를 divisor=3으로 나눈다고 하자.
• multiple=1로 시작, 3을 2배씩하여 34 넘지 않도록 반복 3→6→12→24가 됨. 총 8을 곱하였으므로 multiple=8, divisor=24가 됨.
• 이제 quotient=0에서 시작해서 34에서 24를 빼고, 양수인 동안 12→6→3 순으로 뺀다.
• 34-24=10이 되고 24에 해당하는 multiple=8을 더하여 quotient=8
• 10에서 24, 12는 못 빼지만 6은 뺄 수 있음.
• 10-6=4이 되고 6에 해당하는 multiple=2를 더하여 quotient=10
• 4에서 6은 못 빼지만 3은 뺄 수 있음.
• 4-3=1이 되고 3에 해당하는 multiple=1을 더하여 quotient=11

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 0으로 나누기 예외 처리
        if divisor == 0:
            return 2**31 - 1
        
        # 오버플로우 예외 처리
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
        
        # 결과의 부호 판별
        sign = 1
        if dividend < 0:
            dividend = -dividend
            sign = -sign
        if divisor < 0:
            divisor = -divisor
            sign = -sign
        
        # dividend보다 작거나 같은 가장 큰 divisor의 배수 찾기
        multiple = 1
        while dividend >= (divisor << 1):
            divisor <<= 1
            multiple <<= 1
        
        # 이진 탐색을 사용하여 나눗셈 수행
        quotient = 0
        while multiple > 0:
            if dividend >= divisor:
                dividend -= divisor
                quotient += multiple
            divisor >>= 1
            multiple >>= 1
        
        # 결과에 부호 적용
        return sign * quotient

 

 

5. 배운 점

• 부호가 같을 때 True, 다를 때 False 같은 구조를 짜고 싶을 때 if문을 복잡하게 짤 필요 없이 A is B라고 하면 A, B의 참 거짓이 같을 때만 참이 된다.
• 두 배, 절반 같은 연산은 비트 연산을 이용하면 더 빠르다.
• 결과 값의 범위가 정해져 overflow를 처리해야할 때는 min, max를 적절히 활용할 것.
• ★반복문의 속도
  • for, range가 while문보다 빠르다.
• 이 문제는 다양한 좋은 풀이가 있어 배울거리가 많았다.