코딩테스트 문제: (LeetCode) Sqrt(x) - 자바스크립트

포스팅요약 

1. 문제 및 문제 해석

2. 코드

 

---

1. 문제

문제보러 가기: https://leetcode.com/problems/sqrtx/

출처: https://leetcode.com/ (LeetCode)

 

문제 해석 및 요약

기타 내장함수를 사용하지 않고 주어진 x값과, 제곱을 했을때 가장 가까운 수i 를 구하면 됩니다. (단 i*i<=x )

 

* 문제에서(사이트에서) 명시된 내장함수 외에 자바스크립트에는 sqrt함수도 있으나, 이진탐색으로 문제풀어보시는거 추천드립니다 :)

 

Example 1:

예시 1)
Input: x = 4
Output: 2
Explanation: 2*2=4로 2를 제곱했을때 가장 가까운 숫자혹은 같은 값이 된다.

예시 2)
Input: x = 10
Output: 3
Explanation: 3*3=9로 3을 제곱했을때 가장 가까운 숫자가된다. 4*4=16으로 x보다 크므로 제외된다.

 

---

2. 코드

//이진탐색을 이용함.
var mySqrt = function(x) {
    if(x===0||x===1) return x; 
    let start=0; //시작점
    let end=parseInt(x/2)+1; //끝점
    let mid=0;//중간지점
    
    while(end-start>1){
        mid=parseInt((start+end)/2); 
        if(mid*mid===x){ 
            return mid;
        }else if(mid*mid>x){ 
            end=mid;
        }else if(mid*mid<x){
            start=mid;
        }
        
    }
    return start;
};

 

코드 해석

만약 x=10일때

=> start=0, end=5, mid=2

mid*mid=2*2=4 < x 이므로, 범위는 mid보다 크고 end보다는 작아짐.

 

=> start=2, end=5, mid=3

mid*mid=3*3=9<x 이므로, 위와 마찬가지로 범위는 mid부터 end까지.

 

=>start=3, end=5, mid=4

mid*mid=4*4=16>x 이므로, x값보다 커지므로 범위는 start부터 mid까지.

 

=>start=3, end=4

end와 start사이에는 아무런 정수가 없으며, i*i<=x 이여야 하므로,

return start;

---

도움이 필요했던 분들에게 도움이 됐길 바래요 !!! :)