문제

제곱근

풀이

1. 정수 n의 제곱근을 구해야 한다
2. 800 자의 숫자를 담아야 한다

800자의 숫자를 담아야 하는데 일반적인 primitive type 의 자료형으로는 담을 수 없고 biginteger 라는 자료형으로 담아야 한다. 그리고 sqrt 함수를 사용하면 제곱근을 구할 수 있다.

		BigInteger n = new BigInteger(sc.next());
        System.out.println(n.sqrt());

너무 간단하게 풀리는데, 이문제는 이분탐색문제이기 때문에 이분탐색으로 풀어주겠다
이분탐색 문제를 푼지가 너무 오래됬고 많이 없었다

	private static BigInteger binarySearch(BigInteger n) {
        BigInteger left = BigInteger.ONE;
        BigInteger right = n;
        BigInteger mid = null;
        while (true) {
            mid = left.add(right).divide(BigInteger.TWO);
            int result = mid.multiply(mid).compareTo(n);
            if (result == 0) {
                break;
            } else if (result == 1){
                right = mid.subtract(BigInteger.ONE);
            } else {
                left = mid.add(BigInteger.ONE);
            }
        }
        return mid;
    }

divide 함수로 mid를 /2 를해준 값을 제곱해준 result와 compare 해서 일치하면 바로 반복문을 탈출해서 mid 값을 출력해주면 된다

전체 코드

전체 코드