문제로

내가 푼 것

상상도 못함

정답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        int left = 1, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;
    }
}

참고

  1. 초기 조건:
  • 입력 값이 0일 경우, 제곱근은 0이므로 바로 반환합니다.
  1. 이진 탐색:
  • left는 1로, right는 x로 초기화합니다. le- ft가 right보다 작거나 같을 때까지 반복합니다.
  • 중간값 mid를 left + (right - left) / 2로 계산합니다.
  • mid * mid가 x와 같으면 mid를 반환합니다.
  • mid의 제곱이 x보다 작으면 left를 mid + 1로 증가시킵니다.
  • 그렇지 않으면 right를 mid - 1로 감소시킵니다.
  1. 반환 값:
  • 반복이 종료된 후 right를 반환합니다. 이 값이 x의 제곱근을 내림한 값입니다.