[Algorithm][LeetCode 69] Sqrt(x)

LeetCode 문제 풀이 - 제곱근 구하기 (Square Root of x)

문제 설명

주어진 비음수 정수 x에 대해, 내장 제곱근 함수 없이 정수 제곱근을 구하고 내림(floor)하여 반환하는 문제입니다.
즉, Math.sqrt, pow(x, 0.5), x ** 0.5와 같은 내장 함수는 사용할 수 없습니다.

Input: x = 4
Output: 2

Input: x = 8
Output: 2

접근 방법

제곱근은 수학적으로 sqrt * sqrt = x를 만족하는 sqrt를 구하는 것과 같습니다.
단, 실수로 정확하게 구하는 것이 아니라, 정수 범위 내에서 내림한 값을 구하는 것이 목표입니다.

따라서 가능한 제곱근 후보를 이진 탐색(Binary Search)으로 좁혀가며 정답을 구할 수 있습니다.

풀이 코드 (JavaScript)

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return 0;
    let low = 1;
    let high = x;
    let mid;
    let answer = 1;
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        let square = mid * mid;
        if (square > x) {
            high = mid - 1;
        } else if (square < x) {
            answer = mid;
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return answer;
};

고려한 경우의 수

1. while (low ≤ high) vs while (low < high)
   

   
   x = 10일 때,
   1단계: mid = 5 → 25 > 10 → high = 4
   2단계: mid = 2 → 4 < 10 → low = 3
   3단계: mid = 3 → 9 < 10 → low = 4
   4단계: mid = 4 → 16 > 10 → high = 3
   
   => low = 4, high = 3 이 되어 종료됨
   
   → 만약 while (low < high) 조건을 사용했다면
   low = 4, high = 4 인 상태에서 종료되어 mid = 4를 검사하지 않고 넘어가므로
   정확한 탐색이 불가능해질 수 있음.
       

2. low = mid / high = mid 로 갱신했을 때
   

   
   x = 10일 때,
   
   1단계: mid = 5 → 25 > 10 → high = 5
   2단계: mid = 3 → 9 < 10 → low = 3
   3단계: mid = 4 → 16 > 10 → high = 4
   4단계: mid = 3 → 9 < 10 → low = 3
   
   => mid가 3으로 계속 반복되며, low/high가 줄어들지 않아 무한 루프 발생
   
   → 이를 방지하기 위해 반드시 low = mid + 1, high = mid - 1 로 갱신해야 함.
       

결론

정수 제곱근을 구할 때는 이진 탐색을 활용해 효율적으로 접근 가능
주의할 점은 다음과 같습니다:

• 반복문 조건은 low <= high 로 해야 마지막 후보값도 탐색 가능
• mid 값을 기준으로 low = mid + 1, high = mid - 1 으로 갱신하여 무한 루프 방지
• mid * mid <= x일 때 정답 후보로 answer = mid 를 저장