Programmers / 정수 제곱근 판별 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 정수 제곱근 판별 (1단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/120817

프로그래머스

 

문제 설명

 

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

 

제한 사항

 

• n은 1이상, 50000000000000 이하인 양의 정수입니다.

 

입출력 예

 

 

입출력 예 설명

 

---

 

나의 풀이

 

처음 풀이

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

long long solution(long long n) {
    long long result = 1;

    for (int i = 1; result <= n; i++) {
        result = i * i;
        if (result == n) return (i + 1) * (i + 1);
    }
    
    return -1;
}

 

처음에는 그냥 단순하게 1부터 제곱된 값을 비교해가면서 풀었다. 하지만 이 코드는 n이 커질 수록 시간이 오래 걸려서 결국 시간초과로 틀렸다.

 

정답 풀이

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

long long solution(long long n) {
    long long result = 1;
    long long j = 1;

    while ((j * j) < n) j *= 10;

    j /= 10;

    for (int i = 1; result <= n; i++) {
        result = (i + j) * (i + j);
        if (result == n) return (i + j + 1) * (i + j + 1);
    }
    
    return -1;
}

 

이 풀이는 n이 커질 수록 시간을 줄이기 위해서 j라는 변수로 n의 크기와 가장 근접한 곳부터 제곱근을 비교하는 풀이로 풀었다.

 

---

※ 알아야 할 것

 

반복문을 사용할 때 시간이 얼마나 소요되는지 계산을 하면서 풀어야겠다는 생각이 들었다.