LeetCode 367(Valid Perfect Square, Python)

1. 문제 링크

• https://leetcode.com/problems/valid-perfect-square/description/

Valid Perfect Square - LeetCode

 

2. 문제 설명

• 양의 정수 num이 주어졌을 때, perfect square면 True를 그렇지 않으면 False를 반환
  • 여기서 perfect square란, x^2 = num이 되는 정수 x가 존재한다는 것을 의미한다. 
  • sqrt같은 built-in library를 사용하진 말것.

3. 처음 풀이

• 가장 naive하게는 num보다 작은 i에 대해 for 문을 돌리면서, i^2 == num인지를 check할 수 있지만,
  • 이렇게 하면 시간복잡도가 올라가고, 실제 leetcode 에서는 time limit이 걸린다.
• binary search로, 점점 경우의수를 좁혀나가는 식으로 풀어야겠다고 생각을 했다.
• 이에 left, right라는 pointer를 두고, mid = (left+right)//2로 둔 뒤에,
  • 만약 mid를 제곱했을 때 num이 나온다면, True를 반환,
  • 만약 mid를 제곱한 것이 num보다 크다면, pointer를 왼쪽으로 이동시킬 필요가 있다. 
    
    • 예를 들어, 아래 그림처럼 mid가 10이어서, mid를 제곱한 100이 num보다 크다면, pointer는 left와 mid 사이로 이동해야 한다. 
    • 그러므로 right를 mid-1로 이동시켜 준뒤 while문을 반복하면, 0~9 사이의 값 중에서 다시 해를 찾는 과정을 반복할 것이다. 
    • 반대로 mid를 제곱한 값이 num보다 작다면, pointer가 오른쪽으로 이동이 되어야 하고,
      • 이때는 반대로 left = mid+1로 바꾸면서 pointer를 이동시키면 되겠다. 

• 해당 과정을 left <= right인 상황에서 계속 반복하고, 이 때 while문 안에서 True가 반환되거나,
• 반환되지 않고 While문을 빠져나오면 False를 반환하게 된다.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 0, num
 
        while left <= right:
            
            mid = (left+right)//2

            if mid ** 2 == num:
                return True
            
            if mid ** 2 < num:
                left = mid+1
            
            if mid ** 2 > num:
                right = mid-1
        
        return False

4. 다른 풀이

• 출제자의 의도를 벗어난 야매 풀이긴 하지만 (sqrt를 쓰지 말랬으므로), 아래처럼 푼 풀이도 있었다. 

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return float(num ** 0.5).is_integer()

• 대부분의 풀이는 binary search를 사용해서, 위의 처음 풀이와 크게 벗어나는 풀이는 없었다.