[Baekjoon]2417번 정수 제곱근 - Javascript

https://www.acmicpc.net/problem/2417

2417번: 정수 제곱근

문제

정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2^63)

출력

첫째 줄에 q2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다.

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

 

문제풀이(1)

처음엔 간단하게 Math.sqrt를 사용해서 제곱근을 구하면 될 것이라 생각해서 풀어보았다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const n = Number(require("fs").readFileSync(filePath).toString().trim());

// 제곱근을 찾는다.
let result = Math.floor(Math.sqrt(n));

// 제곱근보다 작을 경우 +1을 해준다.
console.log(result ** 2 < n ? result + 1 : result);

 

문제풀이(2)

이진 탐색으로 푸는 방법이 있다고하여 구현해보았다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const n = Number(require("fs").readFileSync(filePath).toString().trim());

const binarySearch = (num) => {
  let low = 0;
  let high = num;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (mid * mid < num) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return low;
};

console.log(binarySearch(n));