[Leetcode] 69. Sqrt(x)

Identifying the Problem

주어진 x의 제곱근을 구한다.

단, 소수점 이후는 잘라 나타내고, pow 함수는 사용하면 안 된다.

 

Constraints:

• 0 <= x <= 2^31 - 1

 

Input: x = 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Organizing thoughts

직관적인 아이디어로 반복문을 사용해 i² == x 거나 i² 이 x를 초과하는 순간을 잡아내면 끝이긴 한데,

 x가 2^31 - 1 인 경우 엄청난 반복을 해야 하고, i를 제곱하는 과정에서 int의 허용범위를 벗어나는 경우가 생겼다.

 

따라서 다른 조건이나 패턴을 찾아보았다.

x를 절반으로 나눈 값은 x의 제곱근이 될 수 없다. 

라는 패턴을 찾을 수 있었다.

 

따라서 중앙값 기준으로 양끝을 조이면 된다.

 

1. 양 끝 기준으로 중앙값 mid을 정하고

2. mid² == x 인 경우 mid 리턴

3. mid² > x 인 경우 끝을 mid - 1로 줄인다.

4. mid² < x 인 경우 처음을 mid +1로 늘린다.

 

단 mid² 와 x를 비교하는 것은 int 범위를 벗어나므로 mid 와 x/mid를 비교한다.  

Sourcecode

int mySqrt(int x)
{



	if(x<2) {return x;}

	int first=1;
    	int end=x;
    	int mid=0;

	while(first<=end) //처음과 끝을 조이는 방식이기에 first가 증가되고 end 가 감소하다보면 
    				  //언젠간 만난다.
	{
        mid=first+(end-first)/2;
        		
		if(mid==x/mid)
			return mid;
        		
		if(mid<x/mid)
	        first=mid+1; //제곱값이 x에 도달하도록 처음값을 증가시킨다.
        		
      	  	else
	        end=mid-1; Q: 왜 과감하게 mid - 1 을 하는가? 
                        	A: 어차피 mid 보다 큰 값은 제곱근이 안된다.
        	
  	}
    	
        return end;
    
    
}