[LeetCode] 제곱근 구하기

문제 링크

Can you solve this real interview question? Sqrt(x) - 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

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

문제 요구 조건

매개변수로 받은 정수의 제곱근을 구하라

제곱근의 소수점 부분은 버리고, 정수로 반환해야된다. ex) 1.444 ⇒ 1

내장함수는 사용하면 안된다.

나의 문제 풀이

내장함수 없이 풀지 못했어요 ㅠ 바로 풀이로 가실게요.

정답 문제 풀이

이 문제를 수학적으로 풀려고 하면 방법이 안 떠오르실 수 있을거 같아요. 이 문제는 이진 탐색 을 활용하면 풀 수 있는 문제에요. 특히 정렬된 배열에서 효과적으로 탐색할 수 있는 알고리즘이죠. 먼저 답안을 보고 설명을 이어가도록 할게요.

정답 풀이 - 이진 탐색

JavaScript

/**
 * @param {number} x
 * @return {number}
 */
function mySqrt(x) {
  if (x < 2) return x;  // sqrt(0) = 0, sqrt(1) = 1

  let left = 1, right = Math.floor(x / 2), ans = 0;

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

    if (sq === x) return mid; // exact square root
    if (sq < x) {
      ans = mid;  // store the last valid candidate
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return ans; // floor of sqrt(x)
}

먼저 0의 제곱근은 0이고, 1의 제곱근의 소수점을 버려도 1이기 때문에 예외처리를 먼저 해줘야해요.

이진 탐색을 위해서는 left 값과 right 값을 알아야 하는데요, 1번에서의 예외처리로 1이 처음 값이 되겠네요.

오른쪽 값으로는 매개변수의 절반값으로 설정하고 x값과 중간값의 비교를해요. 그럼 검색해야하는 부분의 반은 제외함으로서 탐색의 시간을 줄일 수 있어요.

그리고 제곱근 값인 첫 번째 sq를 중간값 mid를 곱해서 비교해 봅니다.

한 번에 제곱근을 찾았을 경우에는 바로 리턴을 해주면 더 시간을 아낄 수 있어요.

만약에 sq가 x보다 작다면, 다시 왼쪽 값을 다시 설정하고 중간값을 구해야되요. 그 반대의 경우에는 오른쪽 값을 설정하고 다시 중간값을 구해야되요.

찾을 때 까지 순회하면 정답이 됩니다. 🙂