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

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

코딩테스트 연습 - 정수 제곱근 판별

---

Think🤔

정수 n에 대해

n이 어떤 정수 x의 제곱인지 아닌지를 판단함

제곱을 판단하는 것은 Math의 내장함수 중에 Math.sqrt()가 존재한다.

Math.sqrt()를 이용해서 150으로 먼저 확인해 본다.

제곱근이 없는 경우 어떻게 나타내는지.. 소수점으로 결과가 나온다.

이러면 양의 "정수" 제곱근이 아닌 것이다.

정수이면서 양수인 것을 제외한 값은 -1이 나오게 해야된다.

---

Solution✍

class Solution {
    public long solution(long n) {
        long answer = 0;
        if((Math.sqrt(n)*10)%10 == 0){
            answer = ((long)Math.sqrt(n)+1) * ((long)Math.sqrt(n)+1);
        }else{
            answer = -1;
        }
        return answer;
    }
}

long타입을 명시하지 않으면 double 형이 되는데 왜 더블형이 되는걸까?

 

Math.sqrt() 메소드는 입력값과 출력값은 모두 double형 으로 나온다고 한다.

고로, 형 변환이 필요한 부분!

 

다른 방법은 없을까? Math.sqrt를 이용하지 않고 제곱근을 구하는 공식을 검색해보았다.

 

조선시대 제곱근 구하는 방법

조선시대 방법이 존재했다.

나눗셈과 뺼셈만으로도 제곱근을 구했다고 한다.

 

제곱근을 구하려고 하는 수를 2로 맨처음에 나눈다!

그리고 1부터 차례대로 나온 값에서 빼주고 그 값이 마이너스가 되기전까지 빼면 제곱근이 나온다고 한다.

바로 적용해 보았다.

 

양의 정수 제곱값은 올바르게 나온다.

제곱이 아니라면 ?

class Solution {
    public long solution(long n) {
        long answer = 0;
        
        // 제곱근
        long root = 0;
        
        // 처음에 2로 나눔
        n = n / 2;
        
        long count = 1;
        
        while(n > 0){
            if(n - count < 0){
                break;
            }
            n -= count;
            root++;
            count++;
        }
        
        root = root+1;
        System.out.println(n + " : " + root);
        if(n*2 != root){
            return -1;
        }
        
        answer = (root+1)*(root+1);
        
        return answer;
    }
}

뭐가 잘못됐을까? Sysout으로 찍어보고 노트에 적어봤는데

n의 값이 5.5가 나와야 되는데 5로 나오고 있엇다.

n	root
60.5	1
59.5	2
57.5	3
54.5	4
50.5	5
45.5	6
39.5	7
32.5	8
24.5	9
15.5	10
5.5	11

class Solution {
    public long solution(long nL) {
        long answer = 0;
        
        // 제곱근
        long root = 1;
        
        // 처음에 2로 나눔 double 형으로 바꿔야 함
        double n = (double)nL / 2;
        
        while(n > 0){
            if(n - root < 0){
                break;
            }
            n -= root;
            root++;
        }
        
        // 남은수의 2를 곱한 값이 while문을 돌린 횟수랑 같으면 제곱근, 아니면 -1
        if(n*2 != root){
            return -1;
        }
        
        answer = (root+1)*(root+1);
        
        return answer;
    }
}

double형으로 바꿔주니 정상적을 작동한것을 확인했다.

 

Math.pow()

Math.pow()함수를 이용하면 더 깔끔하게 짤 수 있다. pow또한 인자 두개를 받고, 둘다 double형이다.

class Solution {
    public long solution(long n) {
        
        double sqr = (int)Math.sqrt(n);
        // 만약 제곱근이 맞으면
        if(Math.pow(sqr,2) == n){
            return (long)Math.pow(sqr+1,2);
        } else{
            return -1;
        }
    }
}

삼항 연산자로 바꿔본다.

class Solution {
    public long solution(long n) {
        double sqr = (int)Math.sqrt(n);
        // 만약 제곱근이 맞으면
        return Math.pow(sqr,2) == n ? (long)Math.pow(sqr+1,2) : -1;
    }
}

---

Review🤩

sqrt의 입력값과 반환값이 double형 타입임을 알게 되었다.

삼항 연산자를 알 수 있었고, 조선 시대 제곱근 구하는 방법도 신박했다!

---