367. Valid Perfect Square

 주어진 양의 정수가 완전한 제곱수인지를 확인하는 문제입니다. 
즉, 어떤 양의 정수 num이 주어질 때, 
이 숫자가 다른 정수의 제곱으로 나타낼 수 있는지 여부를 판단해야 합니다.

예를 들어, 16은 4의 제곱으로 나타낼 수 있으므로 완전한 제곱수입니다. 
반면에 14는 다른 정수의 제곱으로 나타낼 수 없으므로 완전한 제곱수가 아닙니다.


주어진 숫자 num이 1보다 작거나 같은 경우, true를 반환합니다. 왜냐하면 1은 이미 완전한 제곱수입니다.

이진 검색(binary search)을 사용하여 num의 제곱근을 찾습니다. 
즉, num의 제곱근을 sqrt라고 했을 때, 
sqrt * sqrt가 num보다 크면 sqrt를 감소시키고, 
sqrt * sqrt가 num보다 작으면 sqrt를 증가시킵니다.

이 과정을 반복하면서 sqrt * sqrt가 num과 일치하는지를 확인합니다. 
만약 일치하면 num은 완전한 제곱수이며, 그렇지 않으면 아닙니다.

 

public bool IsPerfectSquare(int num) {
    if (num <= 1) {
        return true;
    }

    long left = 1; // 제곱근 후보 시작
    long right = num; // 제곱근 후보 끝

    while (left <= right) {
        long mid = left + (right - left) / 2; // 중간값 계산
        long square = mid * mid;

        if (square == num) {
            return true; // 완전한 제곱수인 경우
        } else if (square < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

 주어진 숫자 num이 완전한 제곱수인지를 확인하기 위해 이진 검색을 사용합니다. 이를 통해 효율적으로 문제를 해결할 수 있습니다.