11일 2번째 (69. 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.

 

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.

 

0 <= x <= 2^31 - 1

 

 

- 음수가 아닌 정수 x가 주어지면 정수 x의 제곱근의 정수부분만 리턴하면 된다.

    class Solution { 
        public int mySqrt(int x) {
            long temp = 1;

            while (true) {
                if (temp * temp > x) {
                    return (int) (temp - 1);
                }
                temp += 1;
            }
        }
    }

 

- 정수 x의 최대범위가 (2^31-1)이므로 int의 음수가 아닌 정수부분 한계치까지 나온다.

- (temp * temp)는 int x가 표현할 수 있는 양의 정수부분을 넘어가기 때문에 int 대신 long을 사용하여야한다.

- (temp * temp) 가 아닌 temp의 경우 int로 형변환해서 리턴하면 끝

- 단점 : 런타임속도가 19ms이다.

 

    class Solution {
        public int mySqrt(int x) {
            return (int) Math.pow(x, 0.5);
        }
    }

- 자바 내장 함수를 사용한 코드

- double로 표현된 x의 0.5 제곱을 정수형변환으로 소수점을 제거한 정수 부분만 리턴한다.

- 차수가 0.5+ 0.5가 더해지면서 1이 되므로 x의 제곱근은 x^0.5이다.

- 런타임 속도가 1ms이다. (위 코드와 메모리 사용량은 같다.)

 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform