프로그래머스 / 두 원 사이의 정수 쌍 / python

def solution(r1, r2):
    answer = 0
    
    zero_line = 0
    n_z = 0
    
    for i in range(r2+1):
        for j in range(r2+1):
            if i == 0:
                if j >= r1:
                    zero_line += 1
            elif j == 0:
                if i >= r1:
                    zero_line += 1
            else:
                if r1**2 <= i**2 + j **2 <= r2 **2:
                    n_z += 1
                    
    return zero_line * 2 + n_z * 4

주어진 입력 조건을 보면 r1, r2의 최대 값은 1,000,000이다. 전부 찾으려면 2,000,000 * 2,000,000, 이므로 시간 복잡도가 너무 크다.

위에 코드는 전부 구하는 대신 x, y 값이 양의 정수 일때만 구한 뒤 곱해주는 방법이다.

하지만 이 방법도 O(n^2)이므로 시간 복잡도가 너무 크다.
실제로 채점해 보면 아래와 같이 시간 초과가 뜬다.

이를 줄이기 위한 방법이 떠오르지 않는다....