(간단한 코드)리트코드 367. Valid Perfect Square

 

해당 문제는 루트 수식을 상용하지 않고서, 해당 숫자가 정수 제곱근이 있는지 알아보는 문제이다.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
    	root_num = num**(0.5) #num에 1/2 승을 제곱해주면, 루트를 하게 된다
        return int(root_num) == root_num 
        #정수형으로 변형해도 수치가 같으면(제외할 소수가 존재하지 않다면), True를 뱉는다

이런 식으로 풀어도 되기는 하지만, 이는 문제의 의도가 아니므로, 다음과 같이 풀겠다.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l, r = 1, num

        while l<=r:
            m = (l+r)//2
            ms = m**2 # ms => m square
            if ms == num:
                return True
            elif ms > num:
                r = m-1
            else:
                l = m+1
        return False

 

우선 이는 리스트가 아니므로, "l과 r"을 숫자 1부터 num까지로 준다.

 

제곱 그림을 다음과 같이 기하급수적으로 커지기 때문에, l과 r의 중간 값인 m은 num의 제곱근 보다 월등히 클 것이다.

실제로 문제에서는 num의 범위는 1부터 시작이므로 0과 1사이의 값이 없다는 것이다.

 

따라서 m의 제곱이 우리가 구하는 숫자보다 클 경우 r = m-1을 해주면 되고, 반대로는 l = m+1을 해주면 된다.

while문을 다 돌았는데도, True를 반환하지 않으면, 해당하는 값이 없다는 것을 의미하고, False를 반환 해주면 된다.