[백준 13706번] 제곱근 - python, js

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

 

💡문제 분석 요약

문제

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

입력

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

출력

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

💡알고리즘 설계

N**(1/2) 와 같은 짧은 방법으로 해결된다면 좋았겠지만 아쉽게도 N이 800자리라 메모리 부족으로 런타임 에러가 발생하게 된다.

이분 탐색을 사용해보자.

1. left=0, right=N
2. mid=(left+right)//2
3. if mid**2==N: print(mid)
4. elif mid**2<N: left=mid+1
5. else: right=mid-1

💡코드

N = int(input())
print(round(N**(1/2)))

런타임 에러(OverflowError)이 뜬다.

N이 800자리로 아주 큰 수 이므로 메모리를 많이 사용해야하기 떄문에, math.isqrt과 같이 정수 연산만 사용하는 방법을 써야한다.

그러나 라이브러리에 의존하고 싶지 않았기 때문에 이분 탐색으로 풀어보았다.

N = int(input())

left, right = 0, N
result = 0

while left <= right:
    mid = (left + right) // 2
    if mid * mid == N:
        result = mid
        break
    elif mid * mid < N:
        left = mid + 1
    else:
        right = mid - 1

print(result)

 

js로도 풀어보았다.

const readline = require("readline");

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  let N;
  for await (const line of rl) {
    N = Number(line);
    rl.close();
  }
  let left = 0;
  let right = N;
  let result = 0;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (mid * mid == N) {
      result = mid;
      break;
    } else if (mid * mid < N) left = mid + 1;
    else right = mid - 1;
  }

  console.log(result);
})();

 

로직은 파이썬 코드와 똑같은데 자꾸 틀렸습니다가 떴다.

Number을 BigInt로 바꾸면 해결된다.

const readline = require("readline");

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  let N;
  for await (const line of rl) {
    N = BigInt(line);
    rl.close();
  }
  let left = BigInt(1);
  let right = N;
  let result = 0;

  while (left <= right) {
    let mid = (left + right) / BigInt(2);
    if (mid * mid == N) {
      result = mid;
      break;
    } else if (mid * mid < N) {
      left = mid + BigInt(1);
    } else right = mid - BigInt(1);
  }

  console.log(result.toString());
})();

 

BigInt는 그대로 출력하면 6n과 같이 뒤에 n이 붙은 채로 출력되기 때문에, toString()으로 문자열로 변환해서 출력해야한다.

💡 느낀점 or 기억할 정보

자바스크립트로 푸니까 예상치 못한 오류가 많이 발생했다.

 

특징	Number	BigInt
정확도	+-2^53 - 1	무제한 크기 지원
연산 방식	부동소수점 기반	정수 연산만 지원
표현 방식	1.5, 1000	1n, 1000n (n으로 표현)