[Java] 69. Sqrt(x)

문제 설명 :

int 값이 하나 주어지고, 이 int 값의 제곱근(제곱근이 소수인 경우 소수점 이하는 버림)을 구하는 문제이다.

 

class Solution {
    public int mySqrt(int x) {

        if(x == 0) return 0;

        long left = 0;
        long right = x;

        while(left <= right){
            long mid = (left+right)/2;

            if(mid*mid == x){
                return (int)mid;
            }else if(mid*mid < x){
                left = mid +1;
            }else if(mid*mid > x){
                right = mid - 1;
            }
        }

        return (int)right;
    }
}

 

해설 :

- 이 문제도 unlike가 상당히 많은 문제인데, 역시나 조건이 명확치 않다.
- 처음에는 완전탐색으로 해결하려했으나, 테스트 케이스 중 Integer 범위를 넘어가는 케이스가 있었고,
Long type으로 변환했으나 runtime error가 발생하는 것으로 보아 애초에 완전탐색으로 풀지 못하도록 하는 문제인 것 같았다.

- 그래서 시간복잡도가 조금 더 낮은 이진탐색을 도입해서 문제를 해결했다.

- 또한, 마지막에 소수점 이하를 버리는 개념을 적용시켜야 하기 때문에 left가 right를 역전한 뒤, right를 출력해 마무리해야했다.