[Kotlin] 정수 제곱근 판별 (프로그래머스 알고리즘)

 

문제

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

 

 

---

 

접근

 

• if문으로 분기 처리하고 제곱근을 구하는 조건만 잘 구하면 될 것 같았다.
• 대충 아래와 같은 느낌?

 

// 구상

class Solution {
    fun solution(n: Long): Long {
                
        if(제곱수인지 구하는 판별 식){
            return (x+1)(x+1)
        } else {
            return -1
        }
        
        
        return 0
    }
}

 

• 제곱수인지 아닌지 판별하는 방식에 대한 생각이 오래 걸렸다.
• 제곱근을 구하는 함수가 있을 것 같았지만, 한 번 내가 아는 함수와 문법을 토대로 알고리즘을 구성하고 싶었다.
• 조선시대에서 제곱수를 구하던 방식 ( 2로 나누고 1부터 차례대로 뺀 뒤 음수가 됐을 때 원래 빼려던 수와 비교)
  ☞ 너무 프로그램에 비효율적인 계산식일 것 같아서 패스
• i를 1부터 (n/2)까지 늘리면서 그 수의 제곱과 들어온 n을 비교하는 방식
  ☞ 이것도 프로그램에 엄청 비효율적인 계산을 많이 할 것 같음
• i를 1부터 (n/2)까지 늘리면서 n을 그 수로 나눴을 때 i인 경우를 찾는 방식
  ☞ 한 번 이 방식을 적용해보기로 시도했다.

 

// 테스트 13, 18 실패
class Solution {
    fun solution(n: Long): Long {
        for(i in 1 .. n/2){         
            if(n / i == i){
                return (i+1) * (i+1)
                break
            }
            if (i == n/2) return -1
        }
        return 0
    }
}


// 전체 성공, BUT 느림
class Solution {
   fun solution(n: Long): Long {
        for (i in 1..n) {
            if (i * i == n) {
                return (i + 1) * (i + 1)
            }
        }
        return -1
    }
}

 

• 처음엔 Long형식의 i가 (i+1)(i+1)을 컴파일 할 수 없었는데, (i+1)*(i+1) 로 수정해주어야 했다. 
• 시간도 오래 걸릴뿐더러, 안타깝게도 테스트 13, 테스트 18에서 실패했다.
• 세 번째 방식을 버리고 두 번째 방식을 차용하니 해결되었지만, 너무 실행 시간이 느리고 비효율적이었다.

 

 

• 근본적으로 이렇게 말도 안되게 수작업으로 계산하는 게 답일리는 없다는 생각이 들었고,
  형을 Float나 Double로 변환해서 제곱 함수인 pow()를 사용해야 하지 않을까... 싶다가
  결국 다른 사람의 풀이를 찾아보게 되었다.
• sqrt(sqaure root)와 pow(power)를 이용한 간단한 풀이었다.

 

---

 

성공 코드

 

import kotlin.math.*
class Solution {
    fun solution(n: Long): Long {
        val a = sqrt(n.toDouble()).toLong()
        return if (a * a == n) (a + 1)*(a + 1) else -1
    }
}

 

---

 

설명

 

1. import kotlin.math.* 를 넣어준다.
2. 제곱근을 구하는 sqrt() 함수를 이용한다.
3. 제곱을 구하는 pow() 함수를 이용할 수도 있다.
4. 참고로 sqrt(), pow() 인수들과 반환형은 Double 형이므로 이점을 사용할 때 주의하여야 한다.
5. toDouble()로 형변환을 하고 제곱근을 구해준 뒤, 다시 정수형으로 toLong()을 하였다.
6. 제곱근이 정수였다면 a * a == n 이 되어 답이 정상적으로 출력되고, 아니면 -1이 출력된다.

 

---

 

다른 방법

 

import kotlin.math.*
class Solution {
    fun solution(n: Long): Long {
        val sqrt = sqrt(n.toDouble())
        return if(sqrt % 1.0 == 0.0) {
            (sqrt + 1).pow(2.0).toLong()
        } else {
            -1
        }
    }
}

• 풀이 코드와 달리 sqrt()와 pow()를 모두 쓴 코드이다.
• sqrt를 1.0으로 나눴을 때 나머지가 없다면 문제에서 원하는 정수 제곱근을 가진 수이다.