🎯문제
x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.
제한 사항
- 1 ≤
r1<r2≤ 1,000,000
입출력 예
| r1 | r2 | result |
|---|---|---|
| 2 | 3 | 20 |
입출력 예 설명
그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.
✏️풀이
코드
class Solution {
public long solution(int r1, int r2) {
long answer = 0;
// 테두리를 체크
for(int i = 1; i <= r2; i++) {
// 작은 원의 테두리를 올림으로 체크
long min = (long)Math.ceil(Math.sqrt(1.0 * r1 * r1 - 1.0 * i * i));
// 큰 원의 테두리를 내림으로 체크
long max = (long)Math.floor(Math.sqrt(1.0 * r2 * r2 - 1.0 * i * i));
// 해당 식을 사용해서 값을 더해줌
answer += (max - min + 1);
}
// 4를 곱해서 반환
return answer * 4;
}
}설명
단순 구현으로 진행하였다.
반복문에서 i는 x좌표이다. 원이 사분면에 있다고 할 때, 1사분면에 찍히는 점들을 모두 구한 뒤 4를 곱해주면 원하는 모든 점을 구할 수 있다.
반복문에서는 작은 원의 테두리를 올림으로, 큰 원의 테두리를 내림으로 체크한다. 작은 원의 경계에 있거나 경계보다 밖에 있어야하기 때문에 올림으로 확인을 하고, 큰 원의 경계에 있거나 경계보다 안에 있어야하기 때문에 내림으로 체크를 한다.
문제의 예시를 가지고 설명해보자면, r1 = 2, r2 = 3일 때 반복문의 값은
i = 1일 때)
root(2 x 2 x 1.0 - 1 x 1 x 1.0) = root(3.0)을 올림하므로 2가 된다.
root(3 x 3 x 1.0 - 1 x 1 x 1.0) = root(8.0)을 내림하므로 2가 된다.
식을 계산해보면 2 - 2 + 1 = 1개의 점이 찍히게 되는 것이다.
이를 i = r2일 때, 즉 i = 3일때까지 반복하여 나오는 모든 값을 더해준다.
이런 식으로 모든 반복이 끝나고 나온 answer에 4를 곱해준 뒤 반환해주면 문제를 해결할 수 있다!
💡느낀 점
수식을 생각해서 푸는 문제였다. 수학은 손을 놓은지 오래되었기에 헷갈리는 부분들을 공부해가면서 해결할 수 있었다. 내가 직접 짠 코드는 꽤나 복잡하고 어디서 꼬였는지 몰랐는데, 참고하다보니 최적화한 풀이가 있어서 이 코드를 공부하는 식으로 블로그를 작성하였다. 세상은 넓고 좋은 코드는 참 많은 것 같다..
링크
