[JAVA] 69. Sqrt(x)

목차

문제

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.

 

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.

 

Constraints:

• 0 <= x <= 231 - 1

풀이

접근방식

• 브루트포스 방식으로 0부터 x/2까지 모든 수를 확인하면 O(n)의 시간복잡도를 가진다.
• 더 나은 시간복잡도를 가질 수 있는 방법은 이진검색(Binary Search)를 사용하는것으로 O(logN)의 시간복잡도를 가진다.

알고리즘

• 1에서 x/2 사이의 범위로 탐색 시작 (제곱근은 주어진 수의 절반보다 클 수 없음)
• 범위의 중간값(mid)을 찾아 x/mid (quotient)
  • 오버플로우를 피하기 위해 곱셈이 아닌 나눗셈으로 값을 찾음 
• if quotient == mid : 정답 발견
• if quotient > mid : start 를 mid로 이동.
• if quotient < mid : end를 mid - 1 로 이동.

class Solution {
    public int mySqrt(int x) {
        
        if (x <= 1){
          return x;  
        }
        
        int start = 1;
        int end = x/2;
        
        while(start < end) {
        
            // start가 변하지 않는 경우, 무한루프에 갇힐 수 있음.
            // 항상 mid를 변경시키기 위해 매 루프마다 mid +1 해줌
            int mid = (start + (end-start)/2) + 1;
            
            // 오버플로우를 피하기 위해 나눗셈 사용
            int div = x/mid;
            
            if(div == mid){
              return mid;  
            }
            
            if(div > mid){
              start = mid;  
            } else{
              end = mid-1;  
            } 
        }
        
        return start;
    }
}

다른 풀이

class Solution {
    public int mySqrt(int x) {
        if (x < 2){
            return x;
        }
        
        int low = 1;
        int high = x/2;
        int mid = 0;
        int result = 0;
        
        while(low<=high){
            mid = (low+high)/2;
            long multiple = mid * (long)mid;
            
            if(multiple == x){
                return mid;
            }
            
            else if(multiple < x){
                low = mid + 1;
                result = mid;
            } else {
                high = mid - 1;
            }
        }
        
        return result;
        
    }
}

주의)

while문 내 mid * (long) mid에서 (long)을 빼면 아래 테스트 케이스에서 실패한다

Input - 2147395599
Output - 1073697799
Expected - 46339

mid * mid 연산은 Integer 범위를 넘을 수 없기 때문에 위와 같이 선언을 해주어야 한다.