367. Valid Perfect Square

num이 정사각형을 만둘 수 있는 숫자인지(ex. 4 => 22, 9 => 33, 16=>4*4, 14 => X) t/f 반환하는 문제이다

첨에 첫번쨰 테케를 보고 16을 예로 들면 1부터 16의 절반 8까지 탐색해서 정사각형을 만들 수 있는지 생각했는데

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        n = num//2
        for i in range(1,n+1):
            if i*i == num:
                return True
            if  i*i > num:
                return False

실패 테.케 : 1

그래서 1부터 num까지 탐색

  class Solution:
    def isPerfectSquare(self, num: int) -> bool:

        for i in range(1,num+1):
            if i*i == num:
                return True
            if  i*i > num:
                return False

성공

시간복잡도
i*i이기 때문에..? O(sqrt(n))

두번째 방법ㅂ은 첫번쨰 아이디어를 약간 보완하여
중간값을 기준으로 탐색하는 방법이다

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = 0
        r= num
        while l<=r:
            m =(l+r)//2
            if m*m>num:
                r=m-1
            elif m*m<num:
                l=m+1
            else:
                return True

시간복잡도는 O(logn)