May LeetCoding Challenge[Day9] - Valid Perfect Square

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

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

Input: 16
Output: true

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 input 숫자가 n*n 인 숫자인가에 관련된 문제이다.

 - 특정 숫자를 고르는 것이기 때문에, 이진탐색을 생각했다.

 - 특정 숫자를 고르는 문제와 같이, 이진탐색을 하는 조건을 알게 되었다.

 - 1~N까지 범위가 주어졌을 때, 숫자 하나를 선택할 때 가장 빠르게 찾기 위해서는 가장 적합하다고 생각하게 되었다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - N을 찾기 위해서 어떤 알고리즘을 사용해야하는가?

 

3. 내가 작성한 알고리즘

 

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num;
        while(left <= right){
            int pivot = left + (right - left) / 2;
            long square = (long)pivot * pivot;
            if(square > num){
                right = pivot - 1;               
            }else if(square < num){
                left = pivot + 1;
            }else if(square == num){
                return true;
            }
        }
        
        return false;
    }
}

4. 내가 작성한 알고리즘 결과

 

 

 

문제 : https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3324/

Explore - LeetCode