[Baekjoon]13706번 제곱근 - Javascript

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

13706번: 제곱근

문제

정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

출력

첫째 줄에 정수 N의 제곱근을 출력한다.

예제 입력 1 복사

36

예제 출력 1 복사

6

예제 입력 2 복사

81

예제 출력 2 복사

9

 

문제풀이(1) - 실패

sqrt 메서드를 사용해서 풀면 될 줄 알았지만 되지 않았다.

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

console.log(Math.sqrt(number.toString()));

 

문제풀이(2)

알고리즘이 잘 생각나지 않아서 검색한 결과 이진탐색으로 풀 수 있다는 것을 알았다.

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

const binarySearch = (number) => {
  let low = 1n;
  let high = BigInt(number);

  while (low <= high) {
    let mid = (low + high) / 2n;

    if (mid ** 2n > number) {
      high = mid - 1n;
    } else if (mid ** 2n < number) {
      low = mid + 1n;
    } else {
      return mid;
    }
  }
};

console.log(binarySearch(number).toString());