[프로그래머스 / 정수 제곱근 판별] Java Script

문제 설명

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

입출력 예

나의 코드

function solution(n) {
 var left = 1;
 var right = n;
 var mid = Math.floor((left+right)/2);
    
    while(left<=right){
        
        if((mid*mid)===n){
            return (mid+1)*(mid+1);
        }
        
        if((mid*mid)<n){
            left=mid+1;
            mid = Math.floor((left+right)/2);
        }
        else if((mid*mid)>n){
            right = mid-1;
            mid = Math.floor((left+right)/2);
        }
    }
    
    return -1;

}

코드 설명

1. 문제 분석

처음엔 Math.sqrt 메소드를 이용하여 쉽게 코드를 짤 수 있겠다는 생각이
들었다. 하지만 입력값 n이 1부터 50000000000000 이하인 양의 정수라는
걸 보고 만약 제곱근이 없는 경우라면 1부터 n까지 반복문을 도는 상황이
발생하게되어 시간복잡도가 꽤 커질거라는 생각이 들었다.
그래서 필자는 이분법을 사용하여 탐색을 한다면 시간복잡도를 꽤 줄일 수
있다고 생각이 들어 이분법으로 풀게되었다.

2. 문제 풀이

풀이과정은 간단하다 범위의 최솟값을 1로 지정하고 최댓값을 n으로 지정하
여 범위 내에서 값이 발견되면 제곱근 값을 리턴하고
발견되지 않은 경우에는 -1을 리턴하도록 설정하였다.