[Swift] O(1)로 제곱 수인지 확인하기

숫자가 x의 제곱 수인지 확인하기

특정 수가 x의 제곱 수인지 확인하는 방법은 많습니다.

가장 대표적으로 반복문을 이용하는 것이죠.

while number >= 3 {
    if number % 3 != 0  { return false }
    number /= 3
}

 

이번 포스팅에서는 O(n)이 아닌 O(1)로 숫자가 x의 제곱 수인지 확인하는 방법에 대해 알아보려고 합니다.

(알고리즘 문제를 풀다 알게 된 방법이에요! ㅎㅎ)

 

n이 3의 제곱 수인지 판단한다고 가정합시다.

9는 3의 제곱수입니다. -> 9 % 3 == 0

27은 3의 제곱수입니다 -> 27 % 3 == 0, 27 % 9 == 0

...

 

이 패턴을 살펴보면 (더 큰 3의 제곱수 % 작은 3의 제곱수) 값은 항상 0 입니다.

이는 "더 큰 3의 제곱수"만 찾으면 n이 3의 제곱수라는 것을 판단할 수 있다는 것을 의미합니다.

n이 Int 타입이라면 "Int형이 가질 수 있는 가장 큰 3의 제곱수"를 구하기만 하면 된다는 거죠.

 

Int형이 가질 수 있는 가장 큰 3의 제곱수는 Swift의 pow 메서드와 log10 함수로 구할 수 있습니다.

let maximumPowerOf3 = Int(pow(3, floor(log10(Double(Int32.max))/log10(3))))

log10 함수에 대한 내용은 아쉽게도 홈페이지에 나와있지 않지만

이렇게 많은 log 함수들이 이미 정의되어 있었고 이름만 보고 무엇을 구해주는지 알 수 있었습니다.

 

3 ^ 0 부터 3 ^ 10까지 테스트를 해보면

let maximumPowerOf3 = Int(pow(3, floor(log10(Double(Int32.max))/log10(3))))
for i in 0..<10 {
    let power3 = Int(pow(3.0, Double(i)))
    print("\(maximumPowerOf3) % \(power3) = \(maximumPowerOf3 % power3)")
}

 

제대로 확인이 되는 것을 볼 수 있습니다.

 

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.