[코테 풀이] Sqrt(x)

Q_69) Sqrt(x)

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

1st try: 시간 초과
-> 2147483647 입력했을 때 시간 초과

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;
            if ((int) Math.pow(mid, 2) > x) {
                right = mid - 1;
            } else if ((int) Math.pow(mid, 2) <= x 
                       && (int) Math.pow(mid + 1, 2) > x) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

2nd try: 성공

class Solution {
    public int mySqrt(int x) {
        long left = 0;
        long right = x;
        int res = 0;

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

🙈 풀이 참조한 문제

• binary search 활용하기