Valid Perfect Square

,

Problem

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Example 1

1
2

Input: 16
Output: true

Example 2

1
2

Input: 14
Output: false

Note

Do not use any built-in library function such as sqrt.

My Answer

  • 특정 수의 제곱수 인지 확인 하는 문제.
  • low, high의 중간값 mid를 구한다.
  • num을 mid로 나눈값이 mid보다 작을 경우엔 num의 제곱근이 mid보다 크다는 것이기 때문에, low를 mid+1값으로 할당한다.
  • num을 mid로 나눈값이 mid보다 클 경우엔 num의 제곱근이 mid보다 작다는 것이기 때문에, high를 mid-1값으로 할당한다.
  • 최종적으로 low는 num의 제곱근이거나, 가장 가까운 수가 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public boolean isPerfectSquare(int num) {
        int low=1;
        int high=num;
        
        while(low <= high) {
            int mid = low + ((high-low)/2);
            
            if ( mid < num/mid) {
                low=mid+1;
            } else {
                high=mid-1;
            }
        }
        
        return low*low == num;
    }
}

참고