뭐라도 머리에서 쥐어짜낸다.

Thoughts

14에 뭘 하면 3.742가 될까? (라이브러리 사용X)

14를 2로 나눈다.
7에서 1을 뺀다.
6에서 2르 뺀다.
4에서 3을 뺀다.
1에서 4를 빼야 하지만 음수가 나오니까 멈춘다.
1을 2배 한것이 4와 같지 않으므로 4는 제곱근이 될 수 없다.

근데 이 문제의 경우 완전제곱수인지 아닌지를 판단하는 것이기 때문에
1을 2배 한것이 4와 같지 않다면 바로 리턴하면 되지 않을까?

My Code

public boolean isPerfectSquare(int num) {	
	int number = num;
	int idx = 1;

	num /= 2;
	while(number - idx > 0) {
		num -= idx;
		idx++;
	}

	if(number * 2 != idx) {
		return false; // 완전제곱될 수 없다!
	} else {
		return true; // 완전제곱이다!
	}
}

Result

기본 테스트 케이스 2개는 통과했으나 제출 시 오답.

이 문제는 완벽한 제곱근을 구하는 것이다. 따라서 너무 복잡하게 생각하지 않아도 된다.

class Solution {
    public boolean isPerfectSquare(int num) {	
        int start = 1;
        int end = num;

        while(start <= end) {
            int mid = (start+end) / 2;
            long square = (long)mid * mid;

            if(square == num) {
                return true;
            } else if (square < num) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }

}

우리의 목표는 제곱했을 때 num과 값이 동일한지만 체크하면 된다.
16이 num이라면 1부터 16까지를 범위로 잡고, mid*mid를 한다.
mid가 4일때, 4*4=16이므로 16은 valid perfect square가 된다.

https://mathbang.net/634#gsc.tab=0
이런 거 찾아보면서 했는데 역시 이진탐색으로 분류된 이유가 있었다. 그냥 이진이여~~

최근 프로그래머를 위한 수학이란 책을 읽고 있는데 실제로 체크해야 할 포인트가 따로 있더라.
알고리즘에서도 그걸 내가 알아내고 싶다.