리트코드 - 69. Sqrt(x)

리트코드 - 69. Sqrt(x)

출처 - https://leetcode.com/problems/sqrtx/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

0 이상의 정수 x가 주어졌을 때, x의 제곱근을 내림하여 가장 가까운 정수로 반환합니다.

반환된 정수는 반드시 0 이상이어야 합니다. 내장 지수 함수나 연산자를 사용해서는 안 됩니다.

 

C++에서는 pow(x, 0.5)이나 Python에서는 x ** 0.5와 같은 함수를 사용해서는 안 됩니다.

 

의사코드

if (x == 0)     0 리턴 left = 1 right = x 반복문 시작 (left <= right) mid = left와 right의 중간값 sqrt =  x / mid if (mid == sqrt)     mid 리턴 if (mid < sqrt)     left = mid + 1 if (mid > sqrt)     right = mid - 1 반복문 종료 right 리턴

 

풀이코드

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int sqrt = x / mid;

            if (mid == sqrt) {
                return mid;
            } 
            if (mid < sqrt) {
                left = mid + 1;
            }
            if (mid > sqrt) {
                right = mid - 1;
            }
        }

        return right;
    }
}

 

코드설명

이진 탐색을 이용하여 제곱근을 찾는 로직이다.

먼저 처음값과 x값을 나누어 중간값을 찾고 그 값으로 x로 나눈 값을 sqrt로 둔다.

 

그리고 mid와 sqrt를 비교해보는데, 만약 같은 값이라면 제곱근을 찾은 것이기 때문에 바로 mid값을 리턴한다.

mid가 sqrt 보다 작다면 mid가 원래의 제곱근 값보다 작은 위치에 있다는 의미가 된다.
이는 위 로직상 '작은값(mid) * 큰 값(sqrt) = x'이기 때문에, '원래_제곱근 * 원래_제곱근 = x' 보다 필연적으로 작을 수밖에 없다.

따라서 left를 mid+1 로 옮겨주게 된다.

 

반대의 경우도 마찬가지인데, mid가 sqrt보다 크다면 right을 mid -1 값을 넣어주면 된다.

 

이렇게 좁히다보면 어느순간 left = right = mid 인 순간이 온다.

이 때 mid와 sqrt가 같으면 mid==sqrt에 의해서 위에서 걸러질 것이고, 만약 그렇지 않으면 딱 제곱근이 떨어지지 않는 정수인 것이다.

 

따라서 반복문을 나오기 전에 

if (mid < sqrt) {
    left = mid + 1;
}

이 분기로 들어가서 left + 1 = right = mid 가 되는데, mid는 지역변수이므로 right를 리턴하거나 left - 1을 리턴하면 된다.

 

시간복잡도 - O(log n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int mySqrt(int x) {
        int answer = 1;
        while (answer * answer <= x) {
            answer++;
        }

        return answer - 1;
    }
}

초기에는 이렇게 간단하게 생각했었는데 int형의 범위를 벗어나면 오류가 발생한다.

 

반례

2,147,395,600(46340의 제곱) <= x <= 2,147,483,647(int형의 최댓값)

 

따라서 이진탐색으로 바꿔서 계산하니 정상적으로 계산되었다.

 

정리

정수가 주어질 때 제곱근을 계산하는 방법.

왠지 String으로 변환해서 계산하는 방법도 있지 않을까 싶다.