728x90
https://leetcode.com/problems/valid-perfect-square/
Valid Perfect Square - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
sqrt 함수를 사용하지 않고 num이 제곱근이라면 true 반환하기
bool isPerfectSquare(int num) {
int s = 1, e = num;
while(s <= e){
long long mid = s + (e-s)/2;
if(mid*mid == num) return true;
else if(mid*mid < num) s = mid+1;
else e = mid-1;
}
return false;
}
Binary Search로 했을 경우 굉장히 속도가 빨라진다.
bool isPerfectSquare(int num) {
long long n = 1;
long long r = 1;
while(r <= num){
if(r == num) return true;
n++;
r = n * n;
}
return false;
}
728x90
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode/easy/Simulation] Add Digits (0) | 2022.09.21 |
---|---|
[LeetCode/easy/BinarySearch] Intersection of Two Arrays II (1) | 2022.09.21 |
[LeetCode/easy/BinarySearch] First Bad Version (0) | 2022.09.21 |
[LeetCode/easy/BinarySearch] Sort(x) (0) | 2022.09.20 |
[LeetCode/easy/TwoPointer] Reverse String II (0) | 2022.09.20 |