[LeetCode] Sqrt(x) 개인풀이

문제

양수인 Integer x가 주어질 때 x의 root 값의 정수 부분을 구하세요.

예제 1
입력 4
출력 2

2는 4의 root값

예제 2
입력 8
출력 2

8의 root값은 2.8242... 이기때문에 양의 정수 부분의 값은 2

제약조건
0 <= x <= 2^31 - 1

문제 url
https://leetcode.com/problems/sqrtx

개인 풀이

아쉽게도 이번 문제는 풀어내지 못했습니다. ㅠㅠ

따라서 이번에는 Duscuss에 풀어내신분의 코드를 보고 전략을 이해하고 어떻게 접근하셨는데 이해하였습니다. 이 부분에 대해서 전달드리도록 하겠습니다. 원문 코드는 아래 링크에서 확인가능합니다.

https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution

위 코드에서는 문제를 해결하기 위한 가장 큰 전략은 BinarySearch르 통해 찾는 범위를 줄이는 것입니다. BinarySearch로 원하는 범위는 mid^2 <= x < (mid + 1)^2입니다. 이범위까지 줄일 수 있다면 결과값은 mid가 되는 것입니다. 나누어서 보면 mid^2 <= x 를 먼저 판단하고 x < (mid + 1)^2를 판단합니다.

여기서 문제가 하나더 생깁니다. x의 범위는 양의 Integer 범위이기 때문에 쉽게 mid^2는 Integer 범위를 벗어나게 됩니다. 이걸 해결하기 위 코드에서는 위해서 수식을 변경합니다. mid^2 <= x는 mid로 양쪽을 나누어 mid <= x/mid로 됩니다. x < (mid + 1)^2도 마찬가지로 mid + 1로 양쪽을 나누면 x(mid + 1) < mid + 1가 됩니다.

이를 만족시키는 mid값을 찾기위해 BinarySearch를 left = 1, right = Integer.MAX_VALUE를 기본으로 두고 진행하면 결과값을 얻을 수 있게 됩니다.

코드

해당 코드는 아래와 같습니다.

public int mySqrt(int x) {
    if (x == 0) // 예외 처리
        return 0;
    int left = 1, right = Integer.MAX_VALUE; // left, right 세팅
    while (true) {
        int mid = left + (right - left) / 2; // mid 값 설정, (left + right) / 2로 하지 않은 이유는 (left + right)에서 Integer 범위를 벗어날 수 있기 때문입니다.
        if (mid > x / mid) { // mid^2 <= x를 만족하지 못하면 right를 바꿔 다음 mid값을 떨어뜨려 만족시킬 수 있게 만든다
            right = mid - 1;
        } else {
            if (mid + 1 > x / (mid + 1)) // (mid + 1)^2 <= x를 만족시킨다면 mid를 리턴하며 만족하지 않는다면 left값을 올려 mid값을 변경할 수 있게 한다.
                return mid;
            left = mid + 1;
        }
    }
}

마무리

오늘은 이렇게 LeetCode의 Sqrt(x) 문제를 풀어보는 시간을 가져보았습니다.

저도 BinarySearch까지는 생각했었는데요. Integer 범위를 유지하기 위한 발상이 저에게는 미치지 못했던 부분입니다. 재밌는 수식의 변환을 여러개 볼 수 있었던 문제였습니다. :)

감사합니다.