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

15 March 2020 - less than 1 min read time
Tags: 알고리즘 프로그래머스

문제

주어진 양의 정수 n에 대해서 제곱의 형태로 표현하면 n+1의 제곱을 반환하고 그게 아니면 -1을 리턴

n - 1 ~ 50000000000000 의 범위이고 n=100 이면 121을 반환하고 7이면 -1을 반환

접근

주어진 수는 int에서 해결이 불가능하다.
1 ~ n 사이의 수 가운데 루트 n 을 구하고 그 제곱이 n과 같은지 비교
같다면 (루트 n + 1)의 제곱을 리턴하고 같지 않다면 -1을 리턴

풀이

2가지의 방법으로 풀어보겠습니다.

1번

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 ~ n사이의 수 중 i*i == n 인 수를 찾는다.
문제의 요구사항에 따라 적절한 값을 리턴한다.

2번

long val = (long) Math.sqrt(n) // 

return (val*val) == n ? (val+1)*(val+1) : -1;

Math.sqrt(n)은 기본적으로 double 값이 반환되기에 타입 캐스트 필요하고 그 값이 15.4444 가 나왔다면 val의 값은 소수점이 없어지고 15가 된다.
val*val = n 이 된다면 val는 n 의 제곱근이된다. 문제의 요구사항에 따라 적절한 답을 리턴한다.
Math.pow 까지 활용하여 코드를 더 간결하게 작성할 수 있다.

1번과 2번의 차이는 불필요한 반복의 과정의 유무입니다. 이러한 차이는 실행시간의 큰 차이를 만듭니다. 2번의 실행속도는 0.7~0.8 ms 에서 끝나는 반면 1번의 경우 35.94ms ~ 72.00ms 의 속도가 나옵니다. 즉, 성능의 차이가 최대 10배 까지 일어날 수 있습니다. 그렇기에 문제를 풀 때 효율적이고 최적의 방식을 찾아서 푸는 것이 좋습니다. 만약 그 방식을 모른다면 답을 보고 익숙해지도록 노력하는 것이 중요합니다.