프로그래머스 - 정수 제곱근 판별 java :: 12934

문제 링크

코딩테스트 연습 - 정수 제곱근 판별 | 프로그래머스 (programmers.co.kr)

---

문제 풀이

1번 풀이(바빌로나이법)

public long solution(long n) {
    long count = 30;
    double x = 1.0;
    while(0 < count--) {
        x = (x + (n / x)) / 2;
    }

    return (x % 1 == 0.0) ? (long) ((x+1) * (x+1)) : -1;
}

위 공식은 바빌로니아법 공식입니다.

위의 공식을 반복하면 제곱근의 근사값을 구할 수 있다는 원리입니다.

위의 공식을 예를 들어 설명하겠습니다.

구하고자 하는 값 S=9라고 가정하고, x = 1 부터 시작해서 일정횟수 반복합니다.

✳️ (1.0 + (9 / 1.0)) / 2 = 5.0
✳️ (5.0 + (9 / 5.0)) / 2 = 3.4
✳️ (3.4 + (9 / 3.4)) / 2 = 3.023529411764706
✳️ (3.023529411764706 + (9 / 3.023529411764706)) / 2 = 3.00009155413138
✳️ (3.00009155413138 + (9 / 3.00009155413138)) / 2 = 3.000000001396984
✳️ (3.000000001396984 + (9 / 3.000000001396984)) / 2 = 3.0
✳️ (3.0 + (9 / 3.0)) / 2 = 3.0
✳️ (3.0 + (9 / 3.0)) / 2 = 3.0
✳️ (3.0 + (9 / 3.0)) / 2 = 3.0

...

✳️ (3.0 + (9 / 3.0)) / 2 = 3.0

해당 공식을 정리하자면 $(x + (n / x)) / 2$ 를 일정횟수 반복하면 제곱근의 근사값을 구할 수 있습니다.

테스트 처리속도

• 🔥 0.01 ~ 0.04ms

2번 풀이

public long solution(long n) {
    if (Math.pow((int) Math.sqrt(n), 2) == n)
        return (long) Math.pow(Math.sqrt(n) + 1, 2);
    return -1;
}

• double java.lang.Math.pow(double a, double b) : a의 b제곱
  예) Math.pow(2, 3) = 2의 3제곱 = 8

• double java.lang.Math.sqrt(double a) : a의 제곱근
  예) Math.sqrt(4) = 4의 제곱근 = 2

테스트 처리속도

• 🔥 0.04 ~ 0.11ms

---

참고자료

1. 바빌로니아법 - 나무위키 (namu.wiki)

---