프로그래머스 - '두 원 사이의 정수 쌍' [코딩테스트 연습]

# 두 원 사이의 정수 쌍 # 181187 # lv2 # Python

 

# 문제

---

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.

r1 = 2, r2 = 3 / -> 20개

 

# 제한사항

---

• 1 ≤ r1 < r2 ≤ 1,000,000

 

# 풀이

---

첫 번째 풀이

""" 두 풀이 모두 시간초과 발생. """
import math

def solution(r1, r2):
# 첫 번째 풀이
    count = 0
    xy_list = [[i, j] for i in range(-r2, r2+1) for j in range(-r2, r2+1)] 
   # r2 길이의 반지름을 가진 원 내부에 있는 모든 점을 xy_list 에 가져옴. -> 좌표값 리스트는 불필요함!! 

    for i in xy_list:
        x, y = i
        length = math.sqrt(x ** 2 + y ** 2) 
        # (x, y) 까지의 거리를 피타고라스 정리(length = sqrt(x^2 + y^2)로 구함. 
        if length >= r1 and length <= r2: 
        # 만약 점까지의 거리가 r1과 r2 사이면,
            count +=1
            # count
        else:
            pass
    return count
    
def solution(r1, r2):
# 두 번째 풀이 
    count = 0
    # 좌표 리스트를 없애고 다시 작성한 풀이. 
    for x in range(-r2, r2+1):
        for y in range(-r2, r2+1):
            distance_squared = x ** 2 + y ** 2
            if r1 ** 2 <= distance_squared <= r2 ** 2:
                count += 1

    return count

""" 두 풀이 모두 시간초과가 발생.. 
-> 아마 이중 for문을 통해 모든 좌표값을 구하려다 보니 발생한 듯함."""

 

최종 풀이

def solution(r1, r2):
    r1_sqr = r1 ** 2 
    r2_sqr = r2 ** 2
    count = 0
    
    for i in range(0, r1):
        count += int(math.sqrt(r2_sqr - i**2)) - int(math.sqrt(r1_sqr - i**2 - 1))
    for i in range(r1, r2):
        count += int(math.sqrt(r2_sqr - i**2))
    return count * 4 # 1사분면에서 구한 count를 모든 4개의 좌표에 대해 적용하고자 4배수 함.