[LeetCode] Sqrt(x) (java)

문제

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

---

문제[번역]

 

양수 x가 주어집니다 x의 제곱근을 구하세요

소수점이 나오면 소수부분을 버리세요

빌트인 함수나 객체를 쓰면 안됩니다.(Math.pow 같은)

 

 

 

 

---

 

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

 

 

 

 

 

---

제약조건

 

 

0 <= x <= 2^31 - 1

 

 

 

 

---

접근방법

약간 그리디한 방식으로 1부터 계속 제곱을하면서 x값과 비교해서 답을 구했습니다.

ex) x가 8이라면

1*1 = 1

2*2 = 4

3*3 = 9 ====> 처음으로 x보다 큰값 등장

따라서 3-1=2을 출력합니다.

 

ex) x가 17이라면

1*1 = 1

2*2 = 4

3*3 = 9

4*4 =16

5*5 = 25 ====>처음으로 x보다 큰 값 등장!!

따라서 5-1=4를 출력합니다.

 

 

 

---

코드

class Solution {
    public int mySqrt(int x) {
        long start = 1;
        while(true){
            if(start*start > x){
                return (int)(start-1);
            }
            start+=1;
        }
    }
}

 

 

 

---

주의사항

 

int타입으로 하면 start*start에서 오버플러우 발생