BEAKJOON / 백준 - JAVA 13706번 제곱근

2024.11.15기준 - 실버4

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

🟥 풀이

이 문제는 큰 수(길이가 800자리)가 들어올 때, 그 수에 제곱근을 출력하는 문제입니다.

 

문제 접근

• 큰 수를 연산하기 위해 BigInteger를 사용했습니다.
• 자바 9이상은 메소드를 지원해주지만, 자바 8이하는 메소드를 생성해 제곱근을 계산해야됩니다.
• 이진 탐색을 통해 제곱근의 값을 구해줬습니다.

1. 입력 받은 수를 BigInteger에 저장해줍니다.

String str = br.readLine();
BigInteger num = new BigInteger(str);

 

2. 제곱근을 구하기 위해 메소드를 생성합니다.

// 이진 탐색을 통한 제곱근 계산
private static BigInteger sqrt(BigInteger x) {
    BigInteger estimation = BigInteger.ZERO.setBit(x.bitLength() / 2);
    BigInteger subEstimation = estimation;

    while (true) {
        BigInteger tmp = estimation.add(x.divide(estimation)).shiftRight(1);
        if (tmp.equals(estimation) || tmp.equals(subEstimation)) {
            return tmp;
        }

        subEstimation = estimation;
        estimation = tmp;
    }
}

 

이진 탐색을 사용하여 제곱근을 구하기 위해, 초기 추정값을 설정하기 위해 비트 연산자를 사용했습니다.

BigInteger estimation = BigInteger.ZERO.setBit(x.bitLength() / 2);

• x.bitLength()
  
  • BigInteger 객체의 x의 비트 길이를 반환해줍니다. (x를 표현하는 데 필요한 최소 비트 수입니다.)
• x.bitLength() / 2
  • x의 비트 길이의 절반 값을 계산합니다. (제곱근의 대략적인 비트 길이를 추정하는 것입니다.)
• BigInteger.ZERO.setBit()
  • BigInteger.ZERO에 지정된 위치에 비트를 설정하여 새로운 BigInteger를 생성합니다.

새로운 추정값 계산

BigInteger tmp = estimation.add(x.divide(estimation)).shiftRight(1);

• x.divide(estimation)
  • 현재 추정값 estimation로 x를 나눕니다.
• estimation.add(x.divide(estimation))
  • 현재 추정값과 x / estimation를 더해줍니다.
• .shiftRight(1)
  • 결과를 2로 나눕니다.(비트를 오른쪽으로 1칸 이동)

 

 

🟪 코드

package Main;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str = br.readLine();
		
		BigInteger num = new BigInteger(str);
		
		bw.write(sqrt(num).toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 이진 탐색을 통한 제곱근 계산
    private static BigInteger sqrt(BigInteger x) {
        BigInteger estimation = BigInteger.ZERO.setBit(x.bitLength() / 2);
        BigInteger subEstimation = estimation;
        
        while (true) {
            BigInteger tmp = estimation.add(x.divide(estimation)).shiftRight(1);
            if (tmp.equals(estimation) || tmp.equals(subEstimation)) {
            	return tmp;
            }
            
            subEstimation = estimation;
            estimation = tmp;
        }
    }
}