LeetCode Sqrt(x) (JavaScript)

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

문제 설명

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

---

문제 풀이

x의 제곱수를 찾기 위해 먼저 다음과 같은 규칙을 찾을 수 있다.

x = 4 -> 2 -> result : 2

x = 8 -> 2.82... -> result : 2

x = 9 -> 3 -> result : 3

...

x = 15 -> 3.... -> result : 3

x = 16 -> 4 -> result : 4

즉, 중간의 값들의 제곱은 x보다 작거나 같다는 것을 알 수 있다.

이제 x의 값을 1부터 ~ x보다 작거나 같을 경우 까지 계속 증가시키면 큰 수인 경우 x를 1씩 증가시켜 시간초과 오류가 발생할 수 있다.

따라서 효율적인 x를 찾아내기 위해 이분 탐색을 이용하여 x의 범위를 효율적으로 구해야 한다.

---

left = 1, right = Math.floor(x / 2)

left, right를 통해 mid를 구하고 mid의 제곱이 x와 같다면 mid값을 리턴

제곱 값이 x보다 작다면 left의 범위를 늘려 다시 검사 (left = mid + 1)

제곱 값이 x보다 크다면 right의 범위를 줄여 다시 검사 (right = mid - 1)

left <= right인 경우 계속 반복을 해주며 가장 큰 제곱 값을 찾을 수 있도록 하고, 최종적으로 right의 값을 리턴해주면 됨.

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x < 2) {
        return x;
    }

    let [left, right] = [1, Math.floor(x / 2)];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const square = mid * mid;

        if (square === x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return right;
};

---

결론

기준 값의 제곱이 x보다 작아지는 경우의 로직 (위 풀이에서는 squre과 x의 비교)

기준 값을 어떤식으로 관리를 할 것이냐

위 두 가지의 조건을 잘 생각해내는게 중요한 문제인 것 같다.