Sqrt(x) - LeetCode

Problem

1. input: 정수 x

2. output: x의 제곱근 이하의 최대 정수 리턴

3. 내장 함수 사용 불가

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

Idea

먼저 x의 범위가 최대 2^31 -1 이므로 제곱근 이하인지 판단할 때 곱하기가 아닌 나누기를 사용해야한다.

1부터 x의 제곱근 이하인지 판단하는 방법으로 해결은 가능하다. → Sol1

결국 정답의 범위는 1부터 x까지로 정해져 있으므로 이분탐색으로 시간을 줄일 수 있다. → Sol2

Solution

1. 1부터 증가하며 제곱근 이하인지 판다

   class Solution {
       fun mySqrt(x: Int): Int {
           var answer = 1
           while (x / answer >= answer) {
               answer++
           }
           return answer - 1
       }
   }
   

   시간 복잡도: 1 ~ x 순회 = n

   

   ⁉ 한정된 범위 안에서 조건에 맞는 최대값 찾기 → 이분탐색

2. 이분탐색

   class Solution {
       fun mySqrt(x: Int): Int {
           if (x == 0) return 0
           var start = 1
           var end = x
           var mid = (start + end) / 2
           while (start <= end) {
               if (x / mid >= mid) {
                   start = mid + 1
               } else {
                   end = mid - 1
               }
               mid = (start + end) / 2
           }
           return start - 1
       }
   }
   

   시간 복잡도: 이분탐색 = log n

   

Point

1. 두수의 곱/합이 target과 일치한지 확인 → int의 범위를 넘을 수 있음 ⇒ 나누기/빼기 로 변환하여 풀 것