[Swift] Programmers - 정수 제곱근 판별

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

프로그래머스

정수 제곱근 판별

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

 n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

 

* 제한사항 *

n은 1이상, 50000000000000 (50조) 이하인 양의 정수입니다.

 

자, 이 알고리즘 문제를 잘 살펴 봐야하죠

이 알고리즘은 제곱근과 관련된 수학적인 지식을 요구해요.

 

제곱근은 어떠한 수를 제곱하여 원래의 수를 얻는 연산을 말하죠

다시 말해, 제곱근을 구하는 것은 어떤 수의 제곱이 주어졌을 때,

원래의 수를 찾는 것을 이야기합니다.

 

√4 = 2

여기서 √4(루트4) 는 4의 제곱근을 의미하고 그 값은 2라는 거죠

반대로, 2의 제곱은 4이죠 이걸 수식으로 나타내면

2² = 4

2의 제곱은 4이죠?

제곱과 √ (루트)는 서로 반대되는 개념이기 때문에 

루트 4는 어떤 수를 제곱하여 4를 얻을까요?

그렇기 때문에 √4는 2의 제곱이 되는거죠

 

또 다른 예로,

√9 = 3

9의 제곱근은 3입니다.

3을 제곱하면 9가 되기 때문이죠

 

제곱근은 항상 양의 값이 됩니다.

음의 값의 제곱근은 복소수에 속하기 때문에 여기서 다루지 않아요.

스위프트에서는 "sqrt()" 함수를 사용하여 제곱근을 계산할 수 있는데,

이 함수는 Foundation 라이브러리에서 제공해주죠.

 

문제를 하나하나 살펴 봅시다.

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.

요 문제만 보았을 때 양의정수라는건 "0"보다 큰 모든 정수를 이야기 합니다.

즉 1, 2, 3, 4, 5와 같이 양의 방향으로 무한히 이어지는 정수를 의미하고

음의 정수는 반대로 "0"보다 작은 정수를 이야기하는겁니다.

예를 들어, -1, -2, -3, -4와 같은 수들을 의미하죠.

 

위 한줄의 문제만 보았을 때 바로 알 수 있는것은

어떤(임의의) 양의 정수가 / 다른 양의 정수(×)의 제곱인지 여부를 판단해야 한다는거죠.

예를 들어, 4는 2의 제곱(4^2)이므로 양의 정수 x가 2인 경우이며, 

9는 3의 제곱(9^3)이므로 양의 정수 x가 3인 경우입니다. 

그러나 

6은 어떤 양의 정수의 제곱이 아니죠

이유는 어떤 양의 정수를 제곱해도 6이 되지 않기에

6의 경우는 양의 정수 x의 제곱이 아니라고 판단 해서 -1을 반환해야 하는거죠.

덧붙여 설명하자면 가장 가까운 양의 정수의 제곱은 2의 제곱인 4이며, 

6보다 작습니다. 또한, 3의 제곱은 9이며, 6보다 큽니다. 

그러므로 6은 양의 정수의 제곱으로 나타낼 수 없죠.

 

위문제로 이루어진 가장 간단한 방법은 n을 1부터 시작해서,

순차적으로 x를 증가시키면서 x의 제곱이 n과 일치하는지 확인하는 것이죠

즉, 1부터 시작하여 x를 1씩 증가시켜가며 x의 제곱을 계산하고, 

그 값이 n과 같은지 확인하는 것입니다.

예를 들어, n이 16이라면:

x = 1일 때, x의 제곱은 1^2 = 1이므로 일치하지 않습니다.
x = 2일 때, x의 제곱은 2^2 = 4이므로 일치하지 않습니다.
x = 3일 때, x의 제곱은 3^2 = 9이므로 일치하지 않습니다.
x = 4일 때, x의 제곱은 4^2 = 16이므로 일치합니다. 이 때, x는 4입니다.
따라서,

이러한 로직을 사용하여 n이 양의 정수 x의 제곱인지 판단할 수 있겠죠

여기서 1"^(카렛)"2 은 1의 2제곱이라고 부릅니다.

그러나

 1부터 n까지의 모든 양의 정수를 반복 하면서 그 수의 제곱이 n과 일치하는지 확인하는 것은

n이 최대 50000000000000(50조)이므로 이 방법은 매우 비효율적이 되겠죠?

 

대신, 좀 더 효율적인 방법으로 n의 제곱근을 구한 뒤에, 그 제곱근이 정수인지 확인하는 것이 됩니다.

만약 제곱근이 정수라면, n은 양의 정수 x의 제곱이며, 이 경우 x+1의 제곱을 반환하면 되고

그렇지 않으면 -1을 반환하면 되겠죠

스위프트의 내장 함수인 sqrt(_:)를 사용하여 제곱근을 구하고,

그 결과가 정수인지 확인할 수 있습니다.

---

 

먼저 지금까지 로직을 분석했다면 이제 작성해야겠죠?!

먼저 함수를 정의해 줍시다.

func solution(_ n: Int64) -> Int64 {

 

함수 solution을 선언해주고 하나의 입력 매개변수 n을 받아들이고 [받아들이다 = "_" / 값을 넣을때 = " :(콜론) "],

Int64 형식의 값을 반환해줘야겠죠?

int64를 쓰는 이유는 주어진 범위 내의 숫자를 처리하기 위해서입니다.

문제에서는  1 ≤  n  ≤ 500000000000001 ≤ n ≤ 50000000000000 범위의 양의 정수가 주어지므로,

더 큰 범위의 정수를 다루기 위해 Int64를 사용하는 것이 적절한 것이죠.

    let sqrtValue = Int64(sqrt(Double(n))) // n의 제곱근을 구함

다음으로는 입력값 n의 제곱근을 구해야 되겠죠?!

이를 위해서 sqrt(제곱근계산) 함수를 사용하여 Double(실수) 형식으로 변환한 후,

그 값을 다시 Int64로 변환해주면 제곱근의 소수 부분은 버리고 정수 부분만을 얻을 수 있게 되죠.

    if sqrtValue * sqrtValue == n { // 제곱근의 제곱이 n과 일치하는지 확인

이제 구한 제곱근의 제곱이 입력값 n과 같은지를 확인해야되는데

제곱근을 다시 제곱하고 원래의 값과 일치하는지 확인을 해야 해서 

sqrtValue * sqrtValue를 사용했습니다.

제곱근을 구하고 나서 제곱하여 원래의 값과 같은지를 확인하는 이유는

제곱근을 구할 때 소수점 아래 부분이 생길 수 있기 때문이죠.

그래서 정확한 비교를 위해 제곱을 다시 해서 확인 해야하는 것입니다.

        return (sqrtValue + 1) * (sqrtValue + 1) // 양의 정수 x의 제곱이면 (x+1)의 제곱 반환

만약 제곱근의 제곱이 입력값 n과 일치한다면, 이 부분이 실행돼요.

여기서는 양의 정수 x의 제곱이므로, (x+1)의 제곱을 반환하죠

이건 다음 양의 정수 x의 제곱을 찾기 위한 과정입니다.

    } else {
        return -1 // 양의 정수 x의 제곱이 아니면 -1 반환
    }
}

조건문의 else 블록이죠, 만약 제곱근의 제곱이 입력값 n과 일치하지 않는다면,

즉, 입력값 n이 양의 정수 x의 제곱이 아니라면, 문제에서 요구한 대로 -1을 반환하는거에요.

만약, 입력값 n이 양의 정수 x의 제곱이 아니라면, -1을 반환하여 이를 표시하는거죠.

 

총코드는 아래와 같아요.

func solution(_ n:Int64) -> Int64 {
    let sqrtValue = Int64(sqrt(Double(n))) // n의 제곱근을 구함
    if sqrtValue * sqrtValue == n { // 제곱근의 제곱이 n과 일치하는지 확인
        return (sqrtValue + 1) * (sqrtValue + 1) // 양의 정수 x의 제곱이면 (x+1)의 제곱 반환
    } else {
        return -1 // 양의 정수 x의 제곱이 아니면 -1 반환
    }
}

---

제곱근을 사용하지 않고도 아래 코드와 같이 로직을 구성해볼 수 있죠. 

func solution(_ n:Int64) -> Int64 {

    if(n == 1)
    {
        return 4
    }

    for i in 1..<n
    {
        if(n == i * i)
        {
            return (i + 1) * (i + 1)
        }
    }
    return -1
}

n이 1일 경우에는 4를 반환하고,

그렇지 않을 경우 1부터 n까지의 각 정수   
i에 대해 i의 제곱을 n과 비교하여 일치하는지 확인하고, 

일치하는 경우에는 (i+1)(제곱)을 반환하고,

그렇지 않은 경우에는 -1을 반환하는 방법이 있죠.

 

그러나 이 방법은 
n이 작을 때에만 효율적이며, 
n이 매우 커질 경우 성능이 저하될 수 있습니다. 

하지만, 주어진 문제에서 n의 범위가 크지 않은 경우에는 

이 방법을 사용하여 문제를 해결할 수 있는겁니다.