정수 제곱근 판별

문제를 링크로 첨부한다.

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

프로그래머스

정말로 이해가 되지 않는다.

 

누군가 답을 해 줄 수 있다면 언제든 댓글로 부탁드린다. 글을 작성하면서 이해했다.;

 

이 문제는

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

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

이러한 문제다.

 

별 거 아닌 거 같다.

그런데

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

라는 제한 사항이 붙는다.

50조까지 서치해야 할 수 있다.

자, 그럼 어떻게 풀어야 할까?

 

1. 1트 > 시간 초과

public class Solution {
    public long solution(long n) {
        for (int i = 1; i * i <= n; i++) {
            if (i * i == n) {
                return (long) Math.pow(i + 1, 2);
            }
        }
        return -1;
    }
}

 

2. 2트 > 시간 초과

class Solution {
    public long solution(long n) {
        for(int i=1; i<=n/4; i++) {
            if(i * i == n) {
                return (long)Math.pow(i+1,2);
            }
        }
        return -1;
    }
}

 

3. 3트 > 시간 초과

class Solution {
    public long solution(long n) {
        // 짝수인 경우
        if(n % 2 == 0) {
            for(int i=2; i*i<=n; i=i+2) {
                if(i*i == n) {
                    return (long)Math.pow(i+1,2);
                }
            }
        } else {
        // 홀수인 경우
            for(int i=1; i*i<=n; i=i+2) {
                if(i*i == n) {
                    return (long)Math.pow(i+1,2);
                }
            }     
        }
        return -1;
    }
}

 

4. 4트 > 시간 초과

class Solution {
    public long solution(long n) {
        // 짝수인 경우
        if(n % 2 == 0) {
            for(int i=2; i<=n/4; i=i+2) {
                if(i*i == n) {
                    return (long)Math.pow(i+1,2);
                }
            }
        } else {
        // 홀수인 경우
            for(int i=1; i<=n/4; i=i+2) {
                if(i*i == n) {
                    return (long)Math.pow(i+1,2);
                }
            }     
        }
        return -1;
    }
}

 

여기서부터 뭔가 이상하다 느꼈고...

한 숨 잔 뒤 방금 GPT로 풀어 보니 sqrt 함수를 쓰더라.

잊고 있었다.

 

class Solution {
    public long solution(long n) {
        long sqrt = (long) Math.sqrt(n); 

        if (sqrt * sqrt == n) { 
            return (sqrt + 1) * (sqrt + 1); 
        } else {
            return -1; 
        }
    }
}

 

이거는 O(1)이니까 성능이 괜찮다 치자.

 

남의 코드 보는데 3위 정도에 아래 코드가 있었고 궁금해서 돌려 봤다.

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;
  }
}

 

'이 코드도 통과했는데 내 코드가 통과 못 했다고???' 싶어서.

그런데 성능이 진짜 괜찮게 나오는 거 아닌가!!!

정확히 기억은 못 하나 sqrt() 쓰는 거랑 별 차이 없었거나 더 나았던 것도 같다.

 

그런데 저게 어떻게 그럴 수 있는지 진짜 이해가 안 된다.

if(n==1)~ 이 부분은 성능에 전혀 영향이 안 갈 거라 생각이 되고

for문을 보면 얘나 나나 최대 n번까지 반복된다.

나는 1~n, 얘는 2~n-1.

차이가 있다면 있겠지만 나는 시간 초과로 테스트 통과 못 하고 얘는 통과할 정도의 거리는 절대 아니라 생각한다.

 

걸리는 건... 밑의 조건에서 내가 (i*i == n)을 써서 i를 두 번 곱하는 만행을 저질렀다는 거고(수가 커질수록 이 정도 연산은 위험할 것 같다.)...

밑에서는 그냥 n/i, n%i 정도만 한다는 것이다.

 

어떤 연산이든 각각 2번씩 하니까 성능에 차이가 없을 거라고 생각했는데

글을 쓰면서 이해해버렸다.

i*i했을 때 n의 제곱근이 i가 아닌데, 당시 i 값이 50조에 가까울수록... 부하가 걸리겠네.

조건에 i*i<=n을 해 놔서 에러는 안 나지만 시간 초과 충분히 나겠다.

 

글을 쓰면서 답을 찾아버린 케이스1.