[LeetCode] 69. Sqrt(x) (Easy) 풀이

❓ 문제

Given a non-negative integer x x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

pow(x, 0.5) or x ** 0.5.

 

음이 아닌 정수 x x가 주어진다.
리턴타입이 정수형이기 때문에 소수점 이하 자리수는 잘리고 오직 결과의 정수부분만 리턴한다.
pow(x, 0.5) or x ** 0.5.

 

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

 

❗ 내 풀이

/**
 * @param {number} x
 * @return {number}
 */
 var mySqrt = function(x) {
  if(x <= 1) {
    return x;
  }
  for(let i = 1; i <= x ; i++) {
    let mult = i * i;
    if(mult == x) {
      return i;
    } else if(x < mult) {
      return i - 1;
    }
  }
};

Runtime: 126 ms
Memory Usage: 43.8 MB

다른 코드들을 봤는데 나만 for문으로 돌려서 구한 것 같아 런타임시간을 줄여서 구할 수 있는 코드들이 있어서 참고로 들고 왔다. 아직도 for문에만 집착하다니..ㅠㅠㅠ

 

❗ Runtime이 가장 빨랐던 답변과 비교

• Math.sqrt() :  숫자의 제곱근을 반환
• Math.pow() : 제곱한 값을 반환
• Math.floor() : 내림을 반환

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    return Math.floor(Math.sqrt(x))
};

 

❗ Memory 사용이 가장 적었던 답변과 비교

런타임이 가장 짧았던 코드랑 같다.

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let check = Math.sqrt(x)
    check = Math.floor(check)
    return check
};

 

❗ Memory 사용이 가장 적었던 답변과 비교

아래 방법은 위 sqrt함수를 안쓰고 이진탐색을 사용하여 개발하였다.

• 내가 푼 for문으로 모든 수를 훑어보는 방식과 다르게 이진탐색을 통해 구현함으로써 런타임시간을 줄였다.

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x < 2) return x;
    
    let start = 1;
    let end = x;
    
    while (start < end) {
        const mid = Math.floor((start+end)/2);
        const val = mid**2;
        
        if (val === x) {
            return mid;
        }
        
        if (val < x) start = mid+1;
        if (val > x) end = mid;
    }
    
    return end-1;
};

 

 

🚩 Detail

• 날짜 : 2022.06.20
• 난이도 : Easy
• 제목 : Sqrt(x)
• URL : https://leetcode.com/problems/sqrtx/