LeetCode 69(Sqrt(x), Python)

1. 문제 링크

• Sqrt(x) - LeetCode

Sqrt(x) - LeetCode

2. 문제 설명

• 음이 아닌 정수가 x가 주어졌을 때 루트x 보다 작거나 같은 정수 중 최대인 것을 구하기
• 예시) x=4이면 2≤√4＜3이므로 2를 반환
• 예시) x=8이면 2≤√8＜3이므로 2를 반환

3. 처음 풀이

• 단순하게 i=0부터 시작해서 0제곱, 1제곱, 2제곱, ... 이 x보다 커지는 순간을 찾는 아이디어

class Solution:
    def mySqrt(self, x: int) -> int:
        i=0
        while True:
            if x<(i+1)*(i+1): #(i+1)의 제곱이 x보다 커지면 반환, 문제에서 ** 연산을 쓰지 말도록 제한하였음
                return i
            else:
                i+=1 #(i+1)제곱이 아직 x보다 작거나 같으면 그 다음 i에 대해 조사하기

4. 다른 풀이

• 앞에서부터 하나씩 찾는 것보다 절반씩 찾는 이진 검색의 원리를 이용하면 훨씬 빠르게 찾을 수 있음. 

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x // 2 if x > 1 else x

        while l <= r:
            mid = (l + r) // 2
            mid2 = mid * mid

            if mid2 == x:
                return mid
            elif mid2 < x:
                l = mid + 1
            elif mid2 > x:
                r = mid - 1
        
        return r

5. 배운 점

• 이진 검색을 익숙하게 하여 자유자재로 활용할 필요가 있다.