[리트코드 LeetCode] Sqrt(x) (Python)

Sqrt(x)

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/819/
• 분류: Top Interview Questions - Medium - Math 

문제

• 음이 아닌 정수 x가 주어졌을 때 x의 제곱근을 계산해라. 결과는 가장 가까운 정수로 내림하여 반환 값도 음이 아닌 정수여야 한다.
• built-in 연산자나 함수를 사용하지 않고 해결해야 한다.
• type x: int / rtype: int

예시

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.

조건

• 0 <= x <= 2^31 - 1

힌트

• 모든 정수를 탐색해보라.
• 검색 영역을 줄이기 위해 정수의 sorted property(정렬된 성질)를 활용하라.

풀이

1. 이진 탐색 (parametric search)

0부터 x까지의 수를 직접 탐색해서 제곱근에 가장 가까운 수를 찾는다. 0~x에 대한 탐색이므로 굳이 배열을 할당할 필요 없이 start=0, end=x, mid=(start+end)//2로 두고 탐색하면 된다.

mid가 가리키는 수의 제곱이 x보다 작으면 오른쪽 영역(mid+1~end)을 탐색하고, mid가 가리키는 수의 제곱이 x보다 크면 왼쪽 영역 (start~mid-1)을 탐색한다. mid의 제곱과 x가 같다면 바로 mid를 리턴한다.

문제에서 제일 가까운 정수로 내림하라고 했으므로 찾는 값보다 작은 영역을 탐색할 때만 ans 값을 갱신한다.

 

작동 예시

예시 1)

0 1 2 3 4

mid = 2

2*2 = 4이므로 2 반환

 

예시 2)

0 1 2 3 4 5 6 7 8

mid = 4

4*4 > 8이므로 0~3 탐색

mid = 1

1*1 < 8이므로 ans 1로 갱신 / 2~3 탐색

mid = 2

2*2 < 8이므로 ans 2로 갱신 / 3~3 탐색

mid = 3

3*3 > 8 이므로 3~2 탐색 → 종료

ans=2 반환

class Solution(object):
    def mySqrt(self, x):
        start = 0; end = x; ans = 0
        while start <= end:
            mid = (start + end) // 2
            if (mid*mid) > x:
                end = mid - 1
            elif (mid*mid) < x:
                start = mid + 1
                ans = mid
            else:
                return mid
        return ans

Time: O(logn) / Space: O(1)

Runtime: 19 ms (beats 83.64%) / Memory Usage: 13.4 MB (beats 68.1%)

 

제일 가까운 정수에 대한 내림을 다음과 같이 if mid * mid <= x < (mid+1)*(mid+1)로 처리할 수도 있다. 시간복잡도와 공간복잡도는 동일하다.

class Solution(object):
    def mySqrt(self, x):
        l, r = 0, x
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid - 1
            else:
                l = mid + 1

Runtime: 19 ms (beats 83.64%) / Memory Usage: 13.4 MB (beats 68.1%)

 

2. Newton 알고리즘

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/819/discuss/25057/3-4-short-lines-Integer-Newton-Every-Language

r = x
while r*r > x:
	r = (r + x//r) // 2
return r

Runtime: 25 ms (beats 53.22%) / Memory Usage: 13.4 MB (beats 68.1%)