[Java] 자바 알고리즘, 프로그래머스 알고리즘 문제풀이 "정수 제곱근 판별"

정수 제곱근 판별

문제 설명

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

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

제한 사항

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

입출력 예

n return

121 144

3 -1

입출력 예 설명

- 입출력 예#1

121은 정수 11의 제곱이므로, (11+1)를 제곱한 144를 리턴합니다.

- 입출력 예#2

3은 정수의 제곱이 아니므로, -1을 리턴합니다.

나의 풀이

class Solution {
  public long solution(long n) {
      long answer = -1;
      double doubleSqrt = Math.sqrt(n);
      int intSqrt = (int)doubleSqrt;
      return intSqrt == doubleSqrt ? (long)Math.pow(intSqrt+1,2) : -1;  
  }
}

- 이 문제의 푸는 방법은

1. Math 클래스를 이용하는 방법

2. 순수하게 반복문을 이용해서 푸는 방법

두가지가 있는것 같습니다. 저는 Math 클래스를 이용해서 풀었습니다. Math클래스의 sqrt메소드는 double형을 반환합니다. 어떤 숫자가 매개변수로 주어지면 실제 제곱근값이 소수점 포함해서 나오죠. 근데 이렇게 나온 double형 제곱근데이터는 (int)로 형변환하게되면 뒤에 소수점은 날라가고 앞의 정수자리만 가져오게 됩니다. 그 둘을 비교하면 되는 것이죠. 제곱근이 정수인 144같은 숫자가 들어가면 12.0이라는 수를 반환하고 이는 int형 12라는 값과 ==연산시 true를 반환하게 됩니다. 

Math 클래스의 pow 메소드는 제곱할 수와 몇제곱할 수를 파라미터로 넣으면 해당 값을 double형으로 반환합니다. 삼항연산자를 써서 조건만족하면 +1한 값을 제곱하고, 조건을 만족하지 않으면 -1을 반환합니다.

다른사람의 풀이

class Solution {
  public long solution(long n) {
      if(n==1){
          return 4;
      }
      for(long i=2;i<n;i++){
          if(n/i == i && n%i ==0){
              return (i+1)*(i+1);
          }
      }
      return -1;
  }
}

- 이분은 2번째 방법으로 푸신것 같습니다. 보시면 Math클래스가 보이지 않죠!

i라는 값을 계속 증가시키면서 파라미터인 n을 나눠보고 같은 값이 나오는지 확인합니다. 같은값이나오면 i에 1을 더해서 제곱해주는 방식입니다. 그런데 i가 n까지 다 올라갈 필요는 없어보입니다. n/2 +1 까지만 더 줄였다면 훨씬 더 빠른 성능을 보일 것입니다. 왜냐면 n/2+1 이후의 값들은 제곱해봤자 절대로 n 이 나올수 없거든요.

-> 9/2 = 4.5입니다. 4를 제곱해도 16이 나오므로 안되고 혹시 4가 input으로 들어올 가능성을 생각해서 +1을 더해야 할 것입니다.