Songzi Vong
공부 저장소
알고리즘, 자료구조, 정리노트 모음

69. Sqrt(x)

문제

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1: Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2.

Example 2: Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.

Constraints:

0 <= x <= 2^31 - 1

문제 해석

정수 x를 입력하면 x 제곱근을 구하는 문제이다. 딱 나누어 떨어지면 바로 출력하면 되고 만약 Example 2 처럼 딱 떨어지지 않는다면 가장 가까운 정수를 내림해서 출력하면 된다.

생각

  • 먼가를 제곱해서 int x에 가장 가까운 것을 찾아야 한다.
  • 숫자들 중 최적의 해를 찾아야하는데 내림은 어떻게 고려할까?
  • 이진 탐색으로 좁혀나가서 거기서 low 값을 도출해낸다?

구현(self)

class Solution {
public:
    int mySqrt(int x) {
        int low = 0;
        int high = x;


        while(low <= high)
        {
            long long sqrt = low + (high- low) / 2;

            if(sqrt * sqrt == x)
            {
                return sqrt;
            }
            else if(sqrt * sqrt > x)
            {
                high = sqrt - 1;
            }
            else
            {
                low = sqrt + 1;
            }
        }
        return low - 1;
    }
};

코드 설명

  • binary search 를 통해 문제를 풀었다.
  • 여기서 주의할 점은 x 의 범위가 0~2^31 이기 때문에 
    int sqrt = low + (high - low) / 2;
  • 이렇게 int 형으로 sqrt를 적게 된다면 오버플로우가 발생해버린다. 그렇기 때문에 long long 으로 적어줘야 한다.
  • 마지막 리턴을 할때 직접 계산해 본 결과 최종적으로 low값은 올림을 한 값을 가지게 된다. 그래서 return low -1;을 적어줬다.
  • 뭔가 이렇게 하는게 맞나 의구심이 들어서 정답도 공부했다.

구현(solution)

class Solution {
public:
    int mySqrt(int x) {
        // For special cases when x is 0 or 1, return x.
        if (x == 0 || x == 1)
            return x;
        
        // Initialize the search range for the square root.
        int start = 1;
        int end = x;
        int mid = -1;
        
        // Perform binary search to find the square root of x.
        while (start <= end) {
            // Calculate the middle point using "start + (end - start) / 2" to avoid integer overflow.
            mid = start + (end - start) / 2;
            
            // Convert mid to long to handle large values without overflow.
            long long square = static_cast<long long>(mid) * mid;
            
            // If the square of the middle value is greater than x, move the "end" to the left (mid - 1).
            if (square > x)
                end = mid - 1;
            else if (square == x)
                // If the square of the middle value is equal to x, we found the square root.
                return mid;
            else
                // If the square of the middle value is less than x, move the "start" to the right (mid + 1).
                start = mid + 1;
        }
        
        // The loop ends when "start" becomes greater than "end", and "end" is the integer value of the square root.
        // However, since we might have been using integer division in the calculations,
        // we round down the value of "end" to the nearest integer to get the correct square root.
        return static_cast<int>(std::round(end));
    }
};

코드 설명

  • 위 코드는 일단 x가 ‘0’ 과 ‘1’이 들어왔을 때를 따로 빼줫다(내가 짠 코드도 Test case에 0과 1을 넣어도 잘 작동한다)
  • 나머지는 비슷하게 binary search를 통해 찾았고 오버플로우를 방지하기 위해 square를 long long 으로 선언한 것을 볼 수 있다.
  • 앞 mid만 괄호 처리가 되어있는 이유는 불필요한 계산을 막기 위함이다. 앞에 mid만 long long 처리를 해주면 자동적으로 곱센 연산이 long long 으로 처리된다고한다.
return static_cast<int>(std::round(end));
  • round 는 가장 가까운 정수로 반올림하는 메소드로 double 을 반환한다.
  • 그렇기 때문에 int형으로 변환시켜줘야한다.

후기

이제 변수들의 타입과 조건으로 오버플로우가 발생할 수 있다라 생각을 하게되었다. 또한 이진 탐색은 정렬된 배열에서만 사용가능하다 이렇게 외웠었는데 최적의 해를 찾는 문제에서도 쓸 수 있다라는 걸 경험했다.

Table of Contents