Leetcode - 69. Sqrt(x) - Easy

이번 문제는 입력받은 숫자의 제곱근을 구하는 문제 입니다.
리턴값은 정수 입니다. 그러니까 소수점 아래 숫자는 없애고 정수만 리턴합니다.
그래서 8의 제곱근은 2.82842... 인데 소수점 아래를 없앤 2가 리턴되게 됩니다.

그렇다면 x 는 a의 제곱보다는 크거나 같고 a+1의 제곱보다는 작은 수가 될 겁니다.

코딩을 하기 전에 Math.pow() 메소드를 알아보겠습니다.

그리고 Math에서는 PI와 E라는 상수가 있다.
E는 자연상수 혹은 오일러 수(Euler's Number)라고 불리고, 값은 무리수이다.

그리고 로그 값을 구하는 Math.log() 메소드도 있다.

이것들을 이용해서 스크립팅을 하면 아래와 같이 할 수 있다.

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

    int left = (int)Math.pow(Math.E, 0.5 * Math.log(x));
    int right = left + 1;
    return (long)right * right > x ? left : right;
  }
}

Python으로 하면 아래와 같이 하면 된다.

from math import e, log
class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = int(e**(0.5 * log(x)))
        right = left + 1
        return left if right * right > x else right

두번쨰 방법은 Binary Search 이다.

이것을 코딩하면 아래와 같이 된다.

JAVA

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

    long num;
    int pivot, left = 2, right = x / 2;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      num = (long)pivot * pivot;
      if (num > x) right = pivot - 1;
      else if (num < x) left = pivot + 1;
      else return pivot;
    }

    return right;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left, right = 2, x // 2
        
        while left <= right:
            pivot = left + (right - left) // 2
            num = pivot * pivot
            if num > x:
                right = pivot -1
            elif num < x:
                left = pivot + 1
            else:
                return pivot
            
        return right

세번째 방법은 아래와 같다.
(문과 출신의 한계로 제대로 수학이 나오면 이해하기 힘들다… 그냥 한번 읽어보고 이런게 있구나 하면서 넘어가야 겠다.)

코딩은 아래와 같습니다.

JAVA

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

    int left = mySqrt(x >> 2) << 1;
    int right = left + 1;
    return (long)right * right > x ? left : right;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = self.mySqrt(x >> 2) << 1
        right = left + 1
        return left if right * right > x else right

네번쨰 방법입니다.

JAVA

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

    double x0 = x;
    double x1 = (x0 + x / x0) / 2.0;
    while (Math.abs(x0 - x1) >= 1) {
      x0 = x1;
      x1 = (x0 + x / x0) / 2.0;
    }

    return (int)x1;
  }
}

Python

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        x0 = x
        x1 = (x0 + x / x0) / 2
        while abs(x0 - x1) >= 1:
            x0 = x1
            x1 = (x0 + x / x0) / 2        
            
        return int(x1)

이 네가지 방법의 Runtime과 Memory는 거의 차이가 없는 것 같다.