[Python] Leetcode 29. Divide Two Integers

이인석·2021년 3월 27일

Problem Solving

목록 보기

2/6

문제

Dividend, Divisor 두 Integer 값을 나누면 되는 간단한 문제이다. 하지만, multiply, divide, percent operation을 사용하면 안되는 제약 조건이 있다. 결과 값으로는 나눈 값의 몫을 출력한다.

입출력

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

풀이

Integer범위, divisor != 0 등의 기본적인 조건과, 내 로직이 성립하기 위한 조건들을 코드 앞부분에 처리했다.

Dividend = Divisor * 몫 + 나머지
기본적인 나눗셈은 위와 같이 표현이 가능한데, 곱셈 대신 Divisor의 제곱 수를 이용하여 뺄셈을 해주는 방식으로 표현이 가능하다. 268/3 을 예시로 들어보자.
위 예시와 같이 나누는 수의 거듭제곱 값을 빼주는 식의 접근이 가능하다.
Dividend 값에 가장 근접한 Divisor의 거듭제곱 수를 구한다.
Dividend 값이 Divisor값보다 작아질 때까지(나머지만 남을 때 까지) Dividend에서 Divisor의 거듭제곱 수를 빼주며 거듭제곱 수를 줄여주는 작업을 반복한다.

분석

먼저, Dividend와 인접한 Divisor의 거듭제곱을 구하기 위해 O(log n)만큼 시간이 필요.
다음으로, Dividend를 Divisor의 거듭제곱 수로 빼주면서 거듭제곱 수를 줄이기 때문에 O(log n)의 시간이 필요.
Total Time Complexity: O(log n)

코드

class Solution:
def divide(self, dividend: int, divisor: int) -> int:
    sign = True
    result = 0
    
    limit = pow(2,31) - 1
    
    if(-(limit + 1) > dividend > limit):
        return -1
    if(divisor == 0 or -(limit + 1) > divisor > limit):
        return -1
    
    if(divisor == 1):
        return dividend
    if(divisor == -1):
        if(dividend > limit + 1):
            return -(limit + 1)
        if(dividend < -limit):
            return limit
        return -dividend
    
    dend = dividend
    sor = divisor
    
    if(sor < 0):
        sor = -sor
        sign = not sign
    if(dend < 0):
        dend = -dend
        sign = not sign
        
    if(sor > dend):
        return 0
    
    a = dend
    b = sor
    
    exp = 1
    while(a >= b):
        exp += 1
        b = pow(sor, exp)
    
    exp -= 1
    b = pow(sor, exp)
    
    while(a >= sor):
        if(a >= b):
            a -= b
            result += pow(sor,exp-1)
        else:
            exp -= 1
            b = pow(sor,exp)
    
    if(sign):
        if(result > limit):
            return limit
        return result
    else:
        return -result