Leetcode 69) Sqrt(x)

07 Sep 2021 in Algorithms

내 답안

• binary search로 찾기.
• 주의할 점, 제곱해줄때 int 범위 넘어갈 수 있으니까 (long) 로 타입 캐스트 해줘야한다.

class Solution {
    public int mySqrt(int x) {
        int left =0;
        int right = x;
        int res= 0;
        while(left<=right){
            int mid= (left+right)/2;
            if((long)mid*mid <= x){
                if((long)(mid+1)*(mid+1)>x){
                    res=mid;
                    break;
                }else{
                    left= mid+1;
                }
            }else{
                right= mid-1;
            }
        }
        return res;

    }
}

다른 답안

• 여기서는 mid가 아니라, right가 반환된다.
• while문에서 벗어나는 조건은 left==right일 때라서 return 을 마지막에 저렇게 깔끔하게 해주면 정답이 반환된다.
• 답이 꼭 있다는 전제가 있으니까, 이렇게 더 간단한 방식으로 풀릴 수 있다.

class Solution {
    public int mySqrt(int x) {
        int left =0;
        int right = x;
        int res= 0;
        while(left<=right){
            int mid= (left+right)/2;
            if((long)mid*mid <= x){
                left= mid+1;
            }else{
                right= mid-1;
            }
        }
        return right;
    }
}

저번에 Binary Search로 안 했을때랑 비교

훨씬 빠름.. 저번엔 nlogn으로 안됐당..