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

1. 문제 설명

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

 

- 제한 사항

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

 

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

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

 

3. 정리

사용하는 변수는 50,000,000,000,000 값의 범위가 int형이 표현하는 값의 범위를 초과하기 때문에 long long을 사용하며 for문을 이용하여 i 변수를 제곱근+1까지 실행한다. 이후에 i-1 = 제곱근, (i-1)*(i-1)이 n값과 일치 하다면  정답을 저장하는 변수에 i*i = (제곱근+1)* (제곱근+1) 값을 일치하지 않는다면 -1을 대입한다.

 

 

전체 시간 복잡도는 for문이 제곱근만큼 반복 하므로 O(√n) 이다.

 

 

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12934