알고리즘 코드카타 130 - 두 원 사이의 정수 쌍

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

프로그래머스

 

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

제한 사항
1 ≤ r1 < r2 ≤ 1,000,000

 

 

이번 문제도 사실상 수학문제에 가까웠다. 하지만 이전에 풀어본 문제와 비슷한 요령으로 풀 수 있었다.

https://youtharchive.tistory.com/143

알고리즘 코드카타 116 - 점찍기

 

위의 문제는 원점에서 특정 거리만큼 떨어진 범위 안에 있는 x, y값이 모두 정수인 좌표의 수를 세는 문제인데 한 지점에서 특정 거리만큼 떨어진 점들의 집합이 원이기 때문이다.

 

같은 요령으로 두 원 사이에 속하는 점들의 갯수를 구해주면 된다.

 

def solution(r1, r2):
    answer = 0
    
    for x in range(1, r2 + 1):
        max_y_r2 = int(((r2**2 - x**2) ** 0.5))+1

 

1사분면의 갯수만 구해준 후, 나머지 부분에 대한 갯수는 곱해서 구할 것이므로 1부터 탐색을 시작한다.

(x = 0 이라는 직선과 접하는 부분을 계산하지 않기 위함이다. 해당 계산식에서 y = 0과 접하는 부분을 계산하므로 x = 0과 접하는 부분의 갯수는 이때 동시에 계산된다.)

 

위의 반복문을 따라 x = 1에서 r2의 반지름의 범위에 속하는 모든 정수로 된 점들의 갯수를 파악 할 수 있다.

 

# def solution(r1, r2):
#     answer = 0
    
#     for x in range(1, r2 + 1):
#         max_y_r2 = int(((r2**2 - x**2) ** 0.5))+1
        min_y_r1 = (r1**2 - x**2) ** 0.5 if x < r1 else 0

 

다음으로 같은  x좌표에서 r1의 반지름 에 속하는 점들의 갯수를 파악한다. 계산 방법 자체는 같지만, x < r1인 경우 실수범위에서 제곱근 연산이 불가능하므로(그래프에서 x값이 r1을 벗어난 구간이다.) 0을 반환하도록 예외처리를 해주어야한다.

 

# def solution(r1, r2):
#     answer = 0
    
#     for x in range(1, r2 + 1):
#         max_y_r2 = int(((r2**2 - x**2) ** 0.5))+1
#         min_y_r1 = (r1**2 - x**2) ** 0.5 if x < r1 else 0
        if min_y_r1 > int(min_y_r1):
            min_y_r1 = int(min_y_r1) + 1
        else:
            min_y_r1 = int(min_y_r1)

 

 

단, r2에 속하는 점들은 포함되어야하기 때문에 정수형으로 바꿔주기만 하면(내림) 되지만 r1에 속하는 점들은 제외되어야하기때문에 (이후에 빼줄예정이므로) 정수형으로 바꾸면서 소수점이 있다면 1을 더해서 올림을 해주어야한다. 

 

# def solution(r1, r2):
#     answer = 0
    
#     for x in range(1, r2 + 1):
#         max_y_r2 = int(((r2**2 - x**2) ** 0.5))+1
#         min_y_r1 = (r1**2 - x**2) ** 0.5 if x < r1 else 0
#         if min_y_r1 > int(min_y_r1):
#             min_y_r1 = int(min_y_r1) + 1
#         else:
#             min_y_r1 = int(min_y_r1)
        
        answer += max_y_r2 - min_y_r1
    
    return answer * 4

 

두 값의 차이를 각 사분면만큼 곱해주면 완료!