[Python 문제 풀이] 프로그래머스 '두 원 사이의 정수 쌍'

Programmers Lv.2 '두 원 사이의 정수 쌍' 파이썬

조건파악

1. 닫힌구간

2. N이 최대 1,000,000이고 내부적으로 sqrt연산이 필요할 것 같다. 따라서 시간복잡도는 최대 O(NlogN)정도 되겠다.

접근

사분면으로 나누어서 하나의 사분면만 생각하자.

x또는 y축 하나를 정해서 1부터 r2까지 축이동하며 스캔하면 편하겠다.

피타고라스 정리를 활용

그러고 나서 축 위의 두 원 사이에 위치한 정수의 개수를 세자.

 

축의 x또는 y좌표가 r1을 넘을 경우 대응되는 치역이 무리수이기 때문에 유효성 검사 장치를 마련하자.

의사코드

i를 1부터 r2까지 1씩 증가시키며 반복

sqrt(r1^2 - i^2)에서 sqrt(r2^2-i^2)까지 정수의 개수를 셈

i가 r1보다 커서 r1^2 - i^2가 음수일 경우 0으로 제한

결과에 4를 곱함

구현

import math 
def solution(r1, r2):
    answer = 0
    for i in range(1, r2 + 1) :
        answer += math.floor((r2**2 - i**2)**0.5) - math.ceil(max(0,r1**2 - i**2)**0.5) + 1
    return answer*4