[LeetCode] 367. Valid Perfect Score

문제

성능 요약

메모리: 16.52MB , 시간: 41ms

 

접근 방법

일단 라이브러리를 사용할 수 없다는 문제 조건으로 시간 복잡도를 어떻게 줄여 나갈 것인가가 관건이라고 생각했다.

제곱근은 주어진 num의 절반보다 작을 것이다.

예를 들어 16의 제곱근인 4는 16의 절반보다 작다.

 

또한 제곱근끼리의 곱셈이 num보다 커진다면 그것은 제곱수가 아니라고 판단했다.

예를 들어 15의 경우 1~8까지 탐색을 하는데, 

i가 4일 경우 16이 되어 15를 넘어가게 되므로 이는 15가 제곱근으로 정수를 갖지 않는다는 것과 같다고 생각했다.

정답

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

 

후기

예외 처리를 제대로 하지 않아 문제가 있었고,  처음에는 그냥 num//2를 통해 범위를 줄이면 통과되거니 싶었지만 시간초과가 나왔다.

이후 i*i > num의 조건을 하나 더 추가하여 시간복잡도를 줄였다.