[level 2] 두 원 사이의 정수 쌍 - 181187
성능 요약
메모리: 10.2 MB, 시간: 628.39 ms
구분
코딩테스트 연습 > 연습문제
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2024년 04월 20일 22:09:23
문제 설명
x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.
제한 사항
- 1 ≤
r1<r2≤ 1,000,000
입출력 예
| r1 | r2 | result |
|---|---|---|
| 2 | 3 | 20 |
입출력 예 설명
그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
풀이
from math import floor, ceil, sqrt
def solution(r1, r2):
answer = 0 # 격자점의 총 수를 저장할 변수 초기화
for i in range(1, r2 + 1): # 1부터 r2까지 반복 (원의 1/4 부분에 대해 계산)
if i < r1: # i가 r1보다 작은 경우, 즉, 내부 원의 범위 안에 있을 때
# r2 원의 x=i에서의 y값 최댓값의 바닥값과
# r1 원의 x=i에서의 y값 최솟값의 천장값 사이의 격자점 수를 계산
answer += floor(sqrt(r2 ** 2 - i ** 2)) - ceil(sqrt(r1 ** 2 - i ** 2)) + 1
else: # i가 r1보다 크거나 같은 경우, 즉, 내부 원이 없는 영역에서
# r2 원의 x=i에서의 y값 최댓값의 바닥값까지의 격자점 수를 계산
answer += floor(sqrt(r2 ** 2 - i ** 2)) + 1
answer *= 4 # 위에서 계산한 것은 원의 1/4에 대한 것이므로, 4를 곱해 전체 격자점 수를 구함
return answer # 계산된 격자점의 총 수를 반환이 문제는 1사분면(x, y > 0) 만 계산한 뒤 * 4 를 해주는 것이 효과적인 방법이라고 생각한다.
math 라이브러리 내의 floor, ceil 함수를 알아보자
- math.floor(x) :
- math.floor 함수는 주어진 실수 x 이하의 가장 큰 정수를 반환한다. 즉, x를 내림하여 가장 가까운 정수로 만든다. 예를 들어, math.floor(3.7) = 3, math.floor(-3.7) = -4 가 된다.
- math.ceil(x)
- math.ceil 함수는 주어진 실수 x 이상의 가장 작은 정수를 반환한다. 즉, x를 올림하여 가장 가까운 정수로 만든다.예를 들어, math.ceil(3.7) = 4, math.ceil(-3.7) = -3 가 된다.
예제에 따르면, i = 1, 2 ,3 이기 때문에
- i = 1 일때는 점이 1개
- i = 2 일때는 점이 3개
- i = 3 일때는 점이 1개
1 <= r1 < r2 <= 1,000,000 이기 때문에
if i < r1 :
- i = 1, (3^2 - 1^2)^1/2 - (2^2 - 1^2) ^1/2 + 1 = (9 - 1) ^ 1/2 + 1 - (4 - 1)^1/2 = 8^1/2 - 3 ^ 1/2 + 1 = 2 - 2 + 1 = 1
if r1 <= i <= r2 : 가 되고.
- i = 2, (3^2 - 2^2)^1/2 + 1 = 5^1/2 + 1 = 2 + 1 = 3
- i = 3, (3^2 - 3^2)^1/2 + 1 = 1
내림올림
r2 보다는 작아야 하고 r1 보다는 커야 한다. 그렇기 때문에 r2와 계산한 식을 내리고, r1과 계산한 식은 올리는 것이다.
이 문제는 스쳐지나가면서 유사한 문제를 몇 번 풀어본 경험이 있던 것 같으나, 제대로 정리 하지 않으니 다시 풀려고 할 때 헤맸었다. 잘 정리해서 다시 유사한 문제를 맞닥들이게 되면 그때는 잘 풀어야 겠다.