[leetcode 69, python] Sqrt(x)

문제 설명

https://leetcode.com/problems/sqrtx/description/

Sqrt(x) - LeetCode

양의 정수 x가 주어질 때 이것의 제곱근 값을 정수로 구하는 문제이다. 단, 내장 함수는 사용하면 안 된다.

 

문제에 나온 두 번째 예시를 들자면 x가 8일 때 8의 제곱근 값은 2.8284... 이다. 이것의 정수(내림)는 2이므로 답은 2가 된다.

문제 풀이

내장 함수를 사용하면 간단하게 풀리겠지만, 사용할 수 없으므로 알고리즘을 사용해야 한다.

나는 이진탐색 알고리즘을 사용했다. 아래는 내가 어떻게 문제를 풀었는지에 대한 설명이다.

 

1. 시작을 1, 끝을 x로 둔다.

2. 가운데 값인 mid를 찾는다.

3. mid를 제곱해서 타겟인 x보다 작은지 확인한다.

4. 만일 작다면 값을 더 늘려서 탐색해도 된다는 의미이니 start을 mid+1로 바꾼다.

5. 만일 크다면 값을 더 줄여서 탐색해야 된다는 의미이니 end를 mid-1로 바꾼다.

6. 2부터 5까지를 start <= end일 때까지 반복한다.

7. end를 반환한다.

 

여기서 end를 반환하는 것에 의문을 가질 수도 있을 거 같다.

 

일단 먼저 내 코드를 보자면 아래와 같다.

class Solution:
    def mySqrt(self, x: int) -> int:
        start = 1
        end = x

        while start <= end:
            mid = (start+end)//2
            if (mid*mid) <= x:
                start = mid+1
            else:
                end = mid-1
        
        return end

 

start가 end와 작거나 같을 때까지 반복문을 돌려주는데, 주목해야 할 점은 저기 (mid*mid) <= x이다.

 

값이 target인 x와 같다 하여도 start를 갱신해주는 것을 알 수 있다. 즉, mid*mid가 x와 같아도 start를 갱신해주는 것이기에 end를 반환해야 한다.

 

또한, 이분 탐색을 풀 때 단순히 mid의 값으로 답을 구한다고 생각할 수 있는데 이분 탐색의 핵심은 값에 근접할 때까지 start와 end를 좁혀주는 것이라고 생각한다. 이렇게 생각하면 mid를 정확하게 구하는 것이 아닌 target의 최댓값 혹은 최솟값을 구하는 문제를 빠르게 접근할 수 있다.

 

코드

python

class Solution:
    def mySqrt(self, x: int) -> int:
        start = 1
        end = x

        while start <= end:
            mid = (start+end)//2
            if (mid*mid) <= x:
                start = mid+1
            else:
                end = mid-1
        
        return end