[Leetcode/파이썬] 69. Sqrt(x)

Sqrt(x)

---

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

• 0 <= x <= 231 - 1

 

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x

        while left <= right :
            mid = (left + right) // 2
            mid2 = mid**2

            if mid2 == x :
                return mid
            elif mid2 > x :
                right = mid - 1
            else :
                left = mid + 1
        return right

x ** 0.5 를 하지마란다. 근데 mid ** 2 하는건 똑같은건 아닌가.. 싶다. 

일단 숫자 제한을 보면 매우 큰 수라는 것을 볼 수 있다. 이러면 우리가 할 수 있는 풀이 방법은 시간 복잡도가 상수이거나 로그 함수이거나. 상수인 경우는 거의 없으니 로그 함수라고 짐작 할 수 있고, 로그 함수인 풀이 방법 중 대표적인 이분탐색을 활용하였다. 

여기서 나는 궁금함을 하나 가질 수 있었다. 여태 문제를 풀어보면서 while left <= right , while left < right 와 같이 <= , < 두개의 경우로 문제가 해결되었다. 어떤 문제는 평상시와 동일하게 풀었음에도 등호 하나 때문에 문제가 해결되지 않는 경우가 많았다. 음 이 부분에 대해선 조금 더 공부해보기로 하자.

----

<, <= 에 대해서 if left == right : 의 경우를 생각해보자. == 이 성립할 경우를 생각해보자. 만약 left == right 일 때 loof 가 계속 돌아야 하는지, 멈춰야 하는지 생각해보고 멈춰야 한다고 생각이 들면 과감하게 <= 를 사용해보자.