[leetcode][367] Valid Perfect Square

문제 : https://leetcode.com/problems/valid-perfect-square/

---

양수 num이 주어졌을 때, num이 완벽한 제곱수면 true, 아닌경우 false를 반환한다. sqrt 함수를 사용하지 않고 풀어라.

---

변수 하나를 1로 초기화시킨 후 제곱 수가 num보다 크거나 커질때까지 1씩 증가한다. 제곱수가 num과 같은 경우 true를 반환하는 방식으로도 풀 수 있다.

 

그리고 이분탐색으로도 풀 수 있다. left = 1, right = num으로 두고 중간 값(m)의 제곱이 num이라면 true를 반환, 작다면 left = m+1,  크다면 right = m-1로 세팅하고 left가 right보다 작거나 큰 경우 이를 반복한다.

left가 right보다 커질 때까지 true를 반환하지 않는 경우 false를 반환한다.

 

시간복잡도는 O(logN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/367.%20Valid%20Perfect%20Square.cpp