๐ ๋ชฉ์ฐจ
๐ค ๋ฌธ์ : Divide Two Integers | LeetCode 820
๋ฌธ์ : https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/820/
๋๋์ ์ฐ์ฐ์๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ๋๋์ ์ ๋ชซ์ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค.
์ด๋ฑํ๊ต์์ ๋ฐฐ์ด.. 10/3 ์ด๋ผ ํ๋ฉด 10-3-3-3.. ํด์ ์์์ผ ๋ ๊น์ง ๋บ ํ์๋ฅผ ๊ตฌํ๋ ๋ฐฉ์์ด ๋ ์ค๋ฅด๋ค์.
1๋ฒ ํ์ด๋ ๊ทธ ํ์ด์์ ๋ฐ๋ณต์ ํ์ฉํ์ฌ ์ฐ์ฐํ์๋ฅผ log๋ก ์ค์ด๋ ๋ฐฉ์์ด๊ณ
2๋ฒ ํ์ด๋ shift์ฐ์ฐ์๋ฅผ ํ์ฉํ ํ์ด์ ๋๋ค.
๐ก ํ์ด
1. ๋บ์ ๋ฐ๋ณต์ ํตํ ๋ชซ ๊ตฌํ๊ธฐ
16/2 ์ ๋ชซ์ ๊ตฌํ๋ค๊ณ ํ๋ฉด 16 - 2- 2 - .... ์ด๋ ๊ฒ 2์ ๋ฐ๋ณตํ์ฌ ๋นผ๊ฒ ์ง์?
์ด์ฐจํผ 2๋ก ๋ฐ๋ณตํด์ ๋บ๊ฑฐ๋ผ๋ฉด, 2*2*2 .. ๋ฑ 2*2^N์ ๋นผ์ ์ฐ์ฐ ํ์๋ฅผ LogN์ผ๋ก ์ค์ผ ์ ์์ต๋๋ค.
2*2^N๋ฅผ ๋บ ํ ๋๋จธ์ง์ ๋ํด์๋ ๋ /2์ ๋ฅผ ํตํด ๋ชซ์ ๊ตฌํด์ ๋ํด์ค๋๋ค.
1. 16/2 = 8
16 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 = 0
๋ชซ : +1 +1 +1 +1 +1 +1 +1 +1 = 8 (2^0 * 8)
16 - 4 - 4 - 4 - 4 = 0
๋ชซ : +2 +2 +2 +2 = 8 (2^1 * 4)
16 - 8 - 8 = 0
๋ชซ : +4 +4 = 8 (2^2 * 2)
16 - 16 = 0
๋ชซ : +8 = 8 (2^3 * 1)
2. 18/3 = 6
18 - 3 - 3 - 3 - 3 - 3 - 3 = 0 (๋ชซ = 1*6)
18 -6 -6 -6 = 0 (๋ชซ = 2*3)
18 -12 =6 (๋ชซ = 4*1)
18 / 3*2*2 ์ธ 12๋ก ๋๋์ ์ ํ์ ๋ ๋๋จธ์ง 6์ด ์๊ฒผ์ต๋๋ค.
์ด ๋๋จธ์ง 6์ ๋ํด์๋ ๊ธฐ์กด์ ๋๋๋ ค๋ ์ 3์ผ๋ก ๋ค์ ๋๋์ ์ ํด์ ๋ชซ์ ๊ตฌํ ํ ๋ํด์ค๋๋ค.
6 - 3 - 3 = 0 (๋ชซ = 1*2)
6 - 6 = 0 (๋ชซ = 2*1)
์ต์ข ๋ชซ์ 4 + 2 ์ธ 6์ด ๋ฉ๋๋ค.
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
## For this problem, if the quotient is strictly greater than 2^31 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -2^31.
# edge case
if dividend == -2**31 and divisor == -1: return 2**31-1
# flag if result shuold be negative(-)
flag = (dividend>0)
flag = flag if (divisor>0) else not flag
def dv(dividend, divisor):
if dividend == 0 : return 0
if dividend < divisor: return 0
quotient = 1
quickDivisor = divisor
while dividend >= quickDivisor+quickDivisor:
quickDivisor += quickDivisor
quotient += quotient
return quotient + dv(dividend-quickDivisor, divisor)
ret = dv(abs(dividend), abs(divisor))
return ret if flag else -ret
2. ๋นํธ์ฐ์ฐ์ ํ์ฉ
๊ฒฐ๊ตญ 1์ ๋ฐฉ๋ฒ์ A/B๋ฅผ ํ ๋
A๋ฅผ ์ด๊ณผํ์ง ์๋ ๊ฐ์ฅ ํฐ B*2^N๋ก ๋๋ ๋ชซ์ ๊ตฌํ๊ณ / ๊ทธ ๋ชซ์๋ 2^N์ ๊ณฑํด์ฃผ๊ณ
๊ทธ ๋๋จธ์ง์ ๋ํ์ฌ B*2^(N-1)๋ก ๋๋ ๋ชซ์๊ตฌํ๊ณ / ๊ทธ ๋ชซ์๋ 2^(N-1)์ ๊ณฑํด์ฃผ๊ณ
..
๊ทธ ๋๋จธ์ง์ ๋ํ์ฌ B*2^1 ๋ก ๋๋ ๋ชซ์ ๊ตฌํ๊ณ / ๊ทธ ๋ชซ์๋ 2^1์ ๊ณฑํด์ฃผ๊ณ
๊ทธ ๋๋จธ์ง์ ๋ํ์ฌ B*2^0 ๋ก ๋๋ ๋ชซ์ ๊ตฌํ๊ณ / ๊ทธ ๋ชซ์๋ 2^0์ ๊ณฑํด์ฃผ๊ณ
ํ๋ ๋ฐฉ์์ด์ฃ ?
B*2^N = B << N ๋ผ๋ ์ ์ ํ์ฉํ์ฌ ๋นํธ์ฐ์ฐ์๋ฅผ ํ์ฉํ ์ฝ๋๋ฅผ ์งค ์ ์์ต๋๋ค.
3 = 11
6 = 3*2 = 110 = 3<<1
12 = 3*2^2 = 1100= 3<<2
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
ans = 0
xx, yy = abs(dividend), abs(divisor)
for i in range(32, -1, -1):
if xx >= (yy<<i):
xx -= (yy<<i)
ans += (1<<i)
if (dividend>0 and divisor<0) or (dividend<0 and divisor>0):
ans = -ans
return min(2**31-1, max(-2**31, ans))
'์๊ณ ๋ฆฌ์ฆ > LEETCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Task Scheduler | LeetCode 826 | Python3 ๐ (0) | 2022.03.17 |
---|---|
Majority Element | LeetCode 824 | Python3 ๐ (0) | 2022.03.16 |
Search a 2D Matrix II | LeetCode 806 | Python3 ๐ (0) | 2022.03.14 |
Search in Rotated Sorted Array | LeetCode 804 | Python3 ๐ (0) | 2022.03.13 |
Coin Change | LeetCode 809 | Python3 ๐ (0) | 2022.03.11 |