[프로그래머스][C++] 제곱수 판별하기

제곱수 판별하기

문제 링크

제곱수 판별하기

분석

어떤 자연수를 제곱했을 때 나오는 정수를 제곱수라고 합니다.

n이 제곱수일 경우 1을 아니라면 2를 반환하는 문제입니다.

제곱수는 16으로 나누었을 때, 나머지는 항상 0, 1, 4, 9 중 하나이며, 이 수가 아니면 제곱수가 될 수 없습니다.
16 미만의 수에서도 적용해볼 수 있지만, 제곱수가 아닌 일부 수에서도 나머지가 0, 1, 4, 9가 나올 수 있어 불완전한 방법입니다.

sqrt함수를 사용하면 제곱근을 구할 수 있으며, 이 제곱근을 다시 곱했을 때 n과 같다면 제곱수가 됩니다.
실수 연산의 오차로 인해 의도한 값이 나오지 않을 수 있으므로, 반올림한 값을 사용하는 것이 좋습니다.
하지만 해당 문제에서는 반올림하지 않아도 테스트 케이스를 통과할 수 있습니다.

풀이

#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 2;
    
    // n에 대한 제곱근을 구한다.
    int x = sqrt(n);

    // 제곱근을 다시 제곱했을 때 n과 같다면 제곱수입니다.
    if (x * x == n)
    {
        answer = 1;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(1)$입니다.

• sqrt함수 $O(1)$

공간 복잡도는 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 3.67MB)
테스트 3 〉 통과 (0.01ms, 4.13MB)
테스트 4 〉 통과 (0.01ms, 3.63MB)
테스트 5 〉 통과 (0.01ms, 4.13MB)
테스트 6 〉 통과 (0.01ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 4.15MB)
테스트 8 〉 통과 (0.01ms, 4.14MB)
테스트 9 〉 통과 (0.01ms, 4.41MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)