문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

음수가 아닌 정수 x가 주어지고, x의 제곱근에 가장 가까운 정수를 내림하여 반환해라. 반환한 정수는 음수가 될 수 없다.
내장된 지수 함수나 연산자를 사용하면 안된다.

• 예를 들면, c++의 pow(x, 0.5) 또는 python의 x ** 0.5는 사용하면 안된다.

Example

#1
Input: x = 4
Output: 2
Explanation: 4의 제곱근은 2이며, 2를 반환한다.

#2
Input: x = 8
Output: 2
Explanation: 8의 제곱근은 2.82842...이고, 가장 가까운 정수로 내림해야해서 2를 반환한다.

Constraints

• 0 <= x <= 2^31 - 1

Solved

이진탐색을 사용해서 문제를 풀어보았다. 중간 값을 제곱했을때 x보다 크거나 작거나 비교해서 제곱근을 찾는 방법이다.

x가 2보다 작은 경우에 먼저 x를 반환해준다. 따로 계산할 필요가 없기 때문이다.

if(x < 2){
  return x;
}

이제 이진탐색에 필요한 정수(L, R, M)를 선언한다. 그리고 결과를 반환할때 사용할 변수 result를 선언한다. 각각의 변수에 1, x / 2, 0, 0을 할당한다.

int L = 1;
int R = x / 2;
int M = 0;
int result = 0;

while문을 통해 이진탐색을 한다.

while(L <= R){
  M = (L + R) / 2;
  long value = (long) M * M;
  
  if(x == value){
    return M;
  } else if (x > value){
    L = M + 1;
    result = M;
  } else {
    R = M - 1;
  }
}

여기선 중간 값을 제곱한 것을 기준으로 탐색한다. 제곱근을 찾는 것이 목적이기 때문이다.

마지막엔 result를 반환한다.

return result;

All Code

class Solution {
    public int mySqrt(int x) {
        if(x < 2){
            return x;
        }

        int L = 1;
        int R = x / 2;
        int M = 0;
        int result = 0;

        while(L <= R){
            M = (L + R) / 2;
            long value = (long) M * M;

            if(x == value){
                return M;
            }else if(x > value){
                L = M + 1;
                result = M;
            }else{
                R = M - 1;
            }
        }

        return result;
    }
}