[ LeetCode - 69 ] Sqrt(x)

https://leetcode.com/problems/sqrtx/description/

Sqrt(x) - LeetCode

문제 푸는데 시간은 많이 안걸렸는데 내 코드는 시간이 오래 걸려서 보니까 다른 풀이 방법은 내가 생각하지 못했다.

특별한 방법은 아닌데 문제를 보고 다양한 풀이 방법을 떠올리는것도 스킬인것 같다.

경험치가 쌓인것 같은데 아직도 모자란걸 보니까...

---

[ 📌 풀이 ]

• Brute-Force

역시나 알고리즘 풀 때 가장 편한 풀이 방법은 완전탐색이다.

1부터 주어진 x까지 반복해서 제곱하여 sqrt 답을 찾아내는 것

• Binary Search

수의 범위가 주어지고 그 내에서 target인 수를 찾는 거니까 이진탐색을 통해서 찾으면 빠르게 찾을 수 있다.

• 수학 공식

이 풀이는 보기만 했지만 수학적으로 접근해서 풀 수도 있다... 난 자신이 없다...(수학 ㅠ)

---

[ 📌 코드 - Python (Brute-Force) ]

class Solution:
    def mySqrt(self, x: int) -> int:
        if not x:
            return 0
        
        if x < 4:
            return 1

        for num in range(x):
            res = num * num

            if res == x:
                return num
            elif res > x:
                return num - 1

[ 📌 코드 - Python (Binary Search) ]

"""
# Author    : Lee In Bok 
# Date      : 2023.11.04(Sat)
# Spend Time: 06m 34s
# Runtime   : 42 ms (Beats 70.84%)
# Memory    : 16.3 MB (Beats 32.40%)
# Algoritm  : Binary Search
"""

class Solution:
    def mySqrt(self, x: int) -> int:        
        ans, srt, end = 0, 0, x

        while srt <= end:
            mid = (srt + end) // 2
            res = mid * mid

            if res == x:
                return mid
            elif res > x:
                end = mid - 1
            else:
                srt = mid + 1
                ans = mid
        return ans

[ 📌 코드 - Java ]

필수로 필요한 부분은 int 타입 대신에 long타입을 사용해야 한다는 것!

int로 제출 했을 때 Time Limit Exceeded로 실패하게 되었는데 이진탐색으로 풀었는데 시간초과가 난게 의아했었다.

 

원인은 큰 수가 들어왔을 때 srt와 end에서 srt가 계속해서 증가하다가 overflow로 숫자가 작아지고 다시 로직을 수행하면서 무한루프를 돌아서 시간이 초과되게 되버린것 같다.

/**
* Author    : Lee In Bok 
* Date      : 2023.11.05(Sun)
* Spend Time: 06m 34s
* Runtime   : 2 ms (Beats 91.16%)
* Memory    : 39.5 MB (Beats 64%)
* Algoritm  : Binary Search
 */
 
class Solution {
    public int mySqrt(int x) {
        long ans = 0;
        long srt = 0;
        long end = x;

        while(srt <= end){
            long mid = (srt + end) / 2;
            long res = mid * mid;

            if(res == x){
                return (int)mid;
            } else if(res > x){
                end = mid - 1;
            } else {
                srt = mid + 1;
                ans = mid;
            }
        } 

        return (int)ans;
    }
}

---

[ 📌 결과 - Python ]

[ Reuslt - Python ]

[ 📌 결과 - Java ]

[ Result - Java ]