[프로그래머스/Lv.2] 두 원 사이의 정수 쌍 - Python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181187#

프로그래머스

두 원의 반지름이 주어지고 두 원 사이에 있는 정수 좌표의 개수를 구하는 문제이다.

 

리뷰

풀이

처음에는 좌표에 대하여 원점으로부터의 거리를 구하고, 그 거리가 r1 이상, r2 이하이면 count하는 방식으로 구했다. 하지만 이 방식은 모든 좌표에 대하여 계산을 하기 위해 이중 for문을 사용하게 되어 시간 초과가 발생했다(케이스 7~10).

 

반복문을 줄이기 위해 각 x 좌표에 대한 두 원의 y 좌표를 각각 구하여 해당 구간 사이의 점 개수를 구했다.

 

코드

import math

def solution(r1, r2):
    
    # 축 위에 있는 점의 개수를 더해야 함
    answer = get_dots(r1, r2)+(r2-r1+1)
    answer *= 4
    
    return answer


# 1사분면 점의 개수 구하는 함수
def get_dots(r1, r2):
    result = 0
    for x in range(1, r2):
        if x < r1:
            r1_y = math.sqrt(r1**2-x**2)
            min_y = math.ceil(r1_y)
        else:
            min_y = 1
            
        r2_y = math.sqrt(r2**2-x**2)
        max_y = math.floor(r2_y)
        
        result+=(max_y-min_y+1)
    
    return result