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

programmers.co.kr/learn/courses/30/lessons/12934

코딩테스트 연습 - 정수 제곱근 판별

 

1. 서론

 

약간은 생각이 필요한 level 1문제. 그렇게 어렵진 않다.

 

2. 문제 풀이

 

양의 정수 n이 주어진다. n이 만약 어떤 정수 x의 제곱이면 x+1의 제곱 값을 return, 아니라면 -1을 return 한다.

예를 들어 n이 121이면 x는 11, 답은 12의 제곱인 144가 된다.

 

처음에는 엄청 쉽게 생각했다. 그냥 for문을 돌려서 i * i = n인 것을 찾으면 될 것 같았다.

그런데 신경 써야 할 포인트가 두 가지 있었다. i의 범위와 시간 초과 관련 문제이다.

처음에 시간초과 때문에 i를 n번 반복하지 말고 n / 2번만 반복했더니 테스트 케이스가 제대로 안 돌았다.

그리고 습관적으로 i를 int형으로 했었는데 생각해보면 범위를 n까지 돌릴 것이기 때문에 i를 long long으로 문제와 똑같이 맞춰줬다.

그리고 그냥 1에서 n까지 돌리면 범위 때문에 당연히 시간초과가 나는 테스트 케이스가 생기는데 이 문제를 처음에는 i++이 아니라 i를 몇 개씩 건너뛰면서 계산해야 하는지 n / 2가 아니라 다른 뭔가가 있는지 골머리를 썩혔는데 그 순간 해결방법이 떠올랐다.

바로 제곱인 수 i를 발견하면 바로 값을 구하고 break 하는 것이다.

 

3. 코드 설명

 

#include <string>
#include <vector>

using namespace std;

long long solution(long long n) {
    long long answer = -1;
    
    for (long long i = 1; i <= n; i++)
    {   
        if (i * i == n)
        {
            answer = (i + 1) * (i + 1);
            break;
        }
    }
    
    return answer;
}

 

코드는 아주 간단하다. i를 long long으로 맞추고 1 같은 수를 위해 <= 로 범위를 맞춘다. 

그리고 만약에 제곱인 수를 발견하면 바로 answer에 답을 계산해서 넣고 for문을 멈춘다. 그렇게 하면 시간초과가 나지 않는다.

 

그리고 다른 사람들은 어떻게 풀었나 코드를 보다가 이런걸 발견했다.

 

#include <string>
#include <vector>
#include <math.h>
using namespace std;

long long solution(long long n) {
    long long answer = sqrt(n);

    return powl(answer, 2) == n ? powl(answer + 1, 2) : -1;
}

 

pow, sqrt 함수가 뭔지 몰라 이 코드를 보고 찾아보았다.

pow 함수는 제곱인 값을 구할 수 있게 해준다. pow(10, 2) => 10 * 10 = 100

sqrt 함수는 pow의 반대다. 루트를 씌워서 제곱근을 구할 수 있게 해 준다. sqrt(121) => 11

헤더는 <cmath> 라고 한다.