[프로그래머스] 정수 제곱근 판별 C++

28 Jan 2023 in Study on Coding Test

시간복잡도를 줄일필요가 있었던 문제

정답제출코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    
    double root = sqrt(n);
    if ((int)root == root)
        answer = (root + 1) * (root + 1);
    else
        answer = -1;
    return answer;
}

오답제출코드 (시간초과)

#include <string>
#include <vector>

using namespace std;

long long IsOK(long long num)
{
    if (num == 1)
        return 1;
    
    for (int i = 2; i * i <= num; ++i)
    {
        if (i * i == num)
            return i;
    }
    return -1;
}

long long solution(long long n) {
    long long answer = 0;
    
    long long root = IsOK(n);
    if (root != -1)
        answer = (root + 1) * (root + 1);
    else
        answer = -1;
    return answer;
}

테스트 케이스 5개가 시간초과되었다.

실패 표시는 뜨지 않고 시간초과만 뜬 것 보니 로직 자체는 맞는거 같은데

아무래도 순회하는 과정에서 시간이 오래걸렸던 것 같았다.

이를 어떻게 줄일지 고민했다.

정답으로의 변환

cmath 라이브러리내에 있는 sqrt함수를 활용하기로 했다.

만약에 sqrt값이 정수가 되었다면 (int)로 강제캐스팅 해도 하기 전의 값과 같을 것이다.

이를 이용해서 정답코드를 제출했다.

추가로, sqrt함수가 어떻게 구현되어있는지 궁금해서 검색해보니

출처를 통해 아래와 같이 구현되었음을 알 수 있었다.

double m_sqrt(double n)
{
    double s=0;
    double t=0;
 
    s = n / 2;
    for (;s != t;)
    {
        t = s;
        s = ( (n / t) + t) / 2;
    }
    return s;
}