Python 구간 사이의 최소 제곱근 찾기

Python 구간 사이의 최소 제곱근 찾기

문제설명

A, B의 두 개 정수 구간 사이에서Square Root의 최대 반복된 적용된 정수값을 반환하면 됩니다.

A가 10, B가 20인 경우에 살펴보면 구간 사이에 10,11,12,13,14,15,16,17,18,19,20 값이 있습니다. 여기서 sqrt가 최대로 적용된 최소 제곱근 정수값을 찾아보면

16은 16->4->2가 되므로, 함수는 2를 반환하면 됩니다.

A가 3000, B가 6000인 경우를 보면 4096은 4096->64->8로 떨어지므로, 함수는 8을 반환하면 됩니다.

A와 B는 2 ~ 1,000,000,000 사이의 값입니다.

[1] math.sqrt를 쓰면 float형이 나온다. 이는 정수로 나눠 떨어지는 것을 확인해보기 위해서는

int(math.sqrt(x) == math.sqrt(x) 조건 검사를 하면 됩니다. 

math.sqrt(99) # 9.9498743710662

특정 구간의 A, B이라면 다음의 코드로 검사가 됩니다.

여기서 제일 작은 값을 반환하면 문제는 풀립니다.

result = [] for i in range(S_A, S_B):         while int(math.sqrt(i)) == math.sqrt(i):             i = math.sqrt(i)             result.append(int(i)) return min(result)

[2] 그러나, 범위가 너무 커진다면 어떻게 해결할 것인가? 구간은 최대 1,000,000,000입니다.

이 구간을 줄이기 위해서 처음 주어진 값에 sqrt를 한 번 더 적용하고 반올림을 취하면

자 그러면 구간은 1,000,000,000에서 31,623 값이 줄어버립니다.

math.sqrt를 적용한 결과이기 때문에 위의 코드와 달리 이 값들도 append도 넣어버리고 시작합니다.

경우1) A = 6000, B = 7000이면 78 ~ 84라는 값이 주어진다. 적은 구간으로 탐색하여 효율적으로 판단이 가능합니다.

[78, 79, 80, 81, 9, 3, 82, 83] 

즉 8000, 9999이라면 90 ~ 100이라는 값이 주어지고

[90, 91, 92, 93, 94, 95, 96, 97, 98, 99] 이 값들도 square root가 적용되었으므로 값을 포함해야 합니다.

def solution(A, B):     S_A = int(math.ceil(math.sqrt(A)))     S_B = int(math.ceil(math.sqrt(B)))     for i in range(S_A, S_B):         result.append(i)         while int(math.sqrt(i)) == math.sqrt(i):             i = math.sqrt(i)             result.append(int(i))     print(result)     return min(result)