BOJ 13706 - 제곱근

문제

완전 제곱수 N이 주어질 때 N의 제곱근을 구하라. N은 최대 800자리 정수이다.

입력

완전 제곱수 N이 주어진다.

출력

N의 제곱근을 출력한다.

예제

입력	출력
`4`	`2`

풀이

Java의 BigInteger.sqrt() 메서드를 사용하여 큰 수의 제곱근을 직접 구한다.

입력을 BigInteger로 읽는다
sqrt() 메서드로 정수 제곱근을 구한다

핵심 아이디어: N이 최대 800자리이므로 일반 정수형으로는 불가능하며, BigInteger의 내장 sqrt 메서드를 사용한다 (Java 9 이상).

코드

package day449;
 
import java.io.*;
import java.math.*;
 
public class Day432BOJ13706제곱근 {
  public static void main(String[] args) throws Exception {
    System.out.println(new BigInteger(new BufferedReader(new InputStreamReader(System.in)).readLine()).sqrt());
  }
} // BigInteger.sqrt() 함수 Java8버전은 불가능

복잡도

시간: O(log N * M) - M은 자릿수, BigInteger 내부 연산
공간: O(M)

문제