백준) 2417 - 정수 제곱근 JS

📌 문제 링크

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

---

📌 문제 탐색하기

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

시간복잡도

• O(log n)

알고리즘 선택

• 이분 탐색

---

📌 코드 설계하기

1. 문제의 `input`을 `BigInt`를 이용해 숫자로 변환합니다.
2. `left`와 `answer`는 `0n`으로 `right`는 `input`으로 초기화합니다.
3. `left`가 `right`보다 클 때까지 반복문을 돕니다.
4. `left`와 `right`를 더해서 `2n`으로 나눈 중간값인 `mid`를 초기화해줍니다.
5. 만약 `mid` 제곱근이 `input`보다 크거나 같다면 `answer`의 값은 `mid`값으로 할당하고 `right`는 `mid`에서 `1n`을 빼서 더 작은 수를 찾습니다.
6. 만약 `mid` 제곱근이 `input`보다 작다면 `left`의 값은 `mid`에서 `1n`을 더해서 더 큰 수를 찾습니다.
7. `answer`의 값을 문자열로 변환하여 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회차

• 숫자 변환을 `BigInt` 대신 `Number`로 했었는데 JS의 부동소수점의 문제로 계속 틀렸다... 
• n의 범위가 0 ≤ n < 2^63 까지라 큰 숫자이니 `BigInt`를 써야한다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/2417
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const input = BigInt(fs.readFileSync(filePath));

let left = 0n;
let right = input;
let answer = 0n;

while (left <= right) {
  const mid = (left + right) / 2n;
  if (mid * mid >= input) {
    answer = mid;
    right = mid - 1n;
  } else {
    left = mid + 1n;
  }
}
console.log(answer.toString());