[LeetCode] - 367. Valid Perfect Square

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Valid Perfect Square" 문제입니다.

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

 

문제 :

Given a positive integer num, return true if num is a perfect square or false otherwise. A perfect square is an integer that is the square of an integer.

In other words, it is the product of some integer with itself. You must not use any built-in library function, such as sqrt.

---

Example 1 :

Input : num = 16

Output : true

Explanation : We return true because 4 * 4 = 16 and 4 is an integer.

 

Example 2 :

Input : num = 14

Output : false

Explanation : We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

 

Constraints : 1 <= num <= 2^31 - 1

---

이 문제는 주어진 정수가 완전 제곱수인지 확인하는 문제입니다. 완전 제곱수는 어떤 정수를 제곱했을 때 나오는 수입니다. 예를 들어, 입력이 16일 경우 4 * 4 = 16이므로 true를 반환하고, 입력이 14일 경우 3.742 * 3.742 ≠ 14이므로 false를 반환합니다. 루트를 쓰면 안 된다는 점 참고해 주시기 바라겠습니다.

class Solution {
    public boolean isPerfectSquare(int num) {
        long i = 1; 
        while (i * i < num) { 
            i++;
        }
        return i * i == num; 
    }
}

 

이 코드는 수학적인 느낌으로 풀어봤습니다 : 

1. 변수 초기화:
   • i를 1로 초기화합니다. 이 변수는 제곱할 숫자를 나타냅니다.
2. 제곱 비교:
   • i의 제곱이 num보다 작을 때까지 i를 증가시킵니다.
   • i * i가 num과 같거나 커지면 반복문을 종료합니다.
3. 결과 반환:
   • i * i가 num과 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

시간 복잡도:

이 코드의 시간 복잡도는 O(√n)입니다. 이유는 i가 1부터 시작하여 i * i가 num보다 크거나 같아질 때까지 1씩 증가하기 때문입니다. i가 num의 제곱근에 도달할 때까지 최대 √n번 반복합니다.

 

---

하지만, 이 문제가 요구하고 원했던 것은 아마 이진 탐색을 이용하여 O(logn)으로 푸는 코드였을 거라고 생각됩니다. 그리하여, 직접 풀지는 않았지만, 그렇게 푼 유저의 코드를 인용해 왔습니다 :

class Solution {
    public boolean isPerfectSquare(int num) {
        long l = 1, r = num;
        while (l <= r) {
            long mid = l + (r - l) / 2;
            if (mid * mid == num) 
                return true;
            else if (mid * mid > num) 
                r = mid - 1; 
            else 
                l = mid + 1;
        }
        return false;
    }
}
// 0xsonu 유저의 코드

 

---

내 코드, 다른 유저 코드 Runtime 결과