[프로그래머스 Lv.1 / C언어] Day11. 정수 제곱근 판별

2024. 05. 28 - 코딩테스트 스터디 Day11

 

 

01. 문제 설명

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

 

 

02. 제한사항

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

 

03. 입출력 예

n	return
121	144
3	-1

 

 

03-1. 입출력 예#1
121은 양의 정수 11의 제곱이므로, (11+1)를 제곱한 144를 리턴합니다.

 

03-2. 입출력 예#2
3은 양의 정수의 제곱이 아니므로, -1을 리턴합니다.

 

 

04. 풀이 및 답

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

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

long long 타입의 x가 0일 때부터 x²이 n과 같거나 작을 때까지 반복문을 돌면서,

x²가 n과 같으면, (x+1)²를, 같지 않으면 -1을 리턴한다.

(이때 x를 long long 타입이 아닌 int 타입으로 선언해 주면 시간 초과가 뜨니 유의해줘야 한다.)

 

 

정답!

 

 

04-2. 풀이 및 답 ★

다른 분들의 풀이를 둘러보다가 제곱근을 구하는 함수인 sqrt()를 사용하신 걸 보고 다시 코드를 짜봤다.

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

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

sqrt() 함수는 인자로 넣은 수의 제곱근을 구해주는 함수이다. 

 

double 타입의 x에 sqrt()함수로 계산한 n의 제곱근을 반환받는다.

(double 타입) x와 int로 형변환 시킨 x의 값이 서로 같으면 n의 제곱근 x가 정수라는 뜻이므로, (x+1)²의 값을 리턴한다.

서로 같지 않으면 -1을 리턴한다.

 

 

역시 정답!

 

 

둘 중 더 효율적인 코드는?

1. 첫 번째 코드의 시간 복잡도: O(√n)
    - x가 n의 제곱근이 될 때까지 하나씩 증가하면서 x * x를 계산
    - 최악의 경우 √n번 반복

2. 두 번째 코드의 시간 복잡도: O(1)
    - sqrt 함수로 n의 제곱근을 한 번에 계산

→ 두 번째 코드가 훨씬 효율적!

 

 

---

 

나는 sqrt() 함수를 모르고 있었어서 문제를 보자마자 두 번째 방식으로 풀 생각을 하지 못했다.

역시 여러 함수들을 잘 파악하고 있어야 효율적이고 좋은 코드를 짤 수 있겠다는 생각을 했다.

 

 

 

공부 열심히 하자 파이팅~