Sherlock and Squares

https://www.hackerrank.com/challenges/sherlock-and-squares/problem?isFullScreen=true

Sherlock and Squares | HackerRank

 

나의 코드 ( 타임 오버 )

#!/bin/python3

import math
import os
import random
import re
import sys

def squares(a, b):
    answer = 0
    for i in range(a, b+1):
        if i**(1/2) == int(i**(1/2)):
            answer+=1
    return answer
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input().strip())
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()
        a = int(first_multiple_input[0])
        b = int(first_multiple_input[1])
        result = squares(a, b)
        fptr.write(str(result) + '\n')
    fptr.close()

 

수정 코드

#!/bin/python3

import math
import os
import random
import re
import sys


import math
def squares(a, b):
    answer = 0
    start = math.ceil(a**(1/2))
    end = math.floor(b**(1/2))
    if end >= start:
        answer = end-start+1

    return answer
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input().strip())
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()
        a = int(first_multiple_input[0])
        b = int(first_multiple_input[1])
        result = squares(a, b)
        fptr.write(str(result) + '\n')
    fptr.close()

 

시간 복잡도

# 수정 전
for i in range(a, b+1) : ( 선형 시간 복잡도 )

# 수정 후
start = math.ceil(a**(1/2)) : ( 상수 시간 복잡도 )
end = math.floor(b**(1/2))

해당 알고리즘 시간복잡도는 상수 시간 복잡도 ( O(1) )