[Level2] 두 원 사이의 정수 쌍 (JAVA)

두 원 사이의 정수 쌍

정답코드

class Solution {
    public long solution(int r1, int r2) {
        long result = 0;
        for(int x = 1; x < r2; x++) {
            double inner = Math.sqrt(Math.pow(r1, 2) - Math.pow(x, 2)); //inner는 r1 원의 방정식에서 찾은 y값
            double outer = Math.sqrt(Math.pow(r2, 2) - Math.pow(x, 2)); //outer는 r2 원의 방정식에서 찾은 y값
            long cnt = (long) outer - (long) inner;
            if(isInteger(inner)) cnt++;
            result += cnt * 4;
        }
        return result + (r2 - r1) * 4;
    }
    private boolean isInteger(double val) {
        return val == (long) val;
    }
}

풀이 과정

원의 방정식은 x^2 + y^2 = r^2입니다.
r의 값은 매개변수로 정해져있고 x값은 반복문으로 제공받으면 원의 방정식을 이용해 y값을 얻을 수 있습니다.

그림에서 빨간색으로 x표시한 점과 아닌 점으로 나눠서 개수를 구하여 문제를 해결하였습니다.

 

빨간색으로 x표시를 하지 않은 점의 개수

설명의 편의를 위해 반지름이 r1인 원의 방정식에서 구한 y값을 inner, r2인 경우 구한 y값을 outer로 부르겠습니다.

원의 방정식을 이용하여 특정 x값일 때 inner, outer값의 유형에 따라 개수가 어떻게 달라지는지 살펴보겠습니다.

 

예) y^2 = r^2 - x^2 했을 때 y값(inner, outer) r1 = 3, r2 = 5, x = 1일 경우 inner = 2.xx = √8 = 9 - 1, outer= 4.xx =√24 = 25 - 1
inner값이 2.xx, outer 값이 4.xx라면 점의 y값은 3, 4이다.
inner값이 2.xx, outer 값이 4라면 점의 y값은 3, 4이다.
inner값이 2, outer 값이 4.xx라면 점의 y값은 2, 3, 4이다.
inner값이 2, outer 값이 4라면 점의 y값은 2, 3, 4이다.
x = n일 때 inner값이 정수일때만 outer - inner + 1 개이고 그 외는 outer - inner라는 것을 알 수 있습니다.

하지만 for문에서 x값이 r1 값보다 커졌을 경우에는 inner값이 Nan이 나와서 정수가 나오지 않아 y = 0인 경우의 개수를 세지 못합니다.
(r1, 0) 을 제외한 y = 0일 때 값은 세지 않고 있다고 생각해주시고 루프를 돌면서 구한 개수 * 4를 총 개수에 더해주면 됩니다.(사분면이기 때문)

 

빨간색 x표시한 점 개수

 

x 표시한 점은 그림에서는 r1과 r2값이 1밖에 차이가 안나서 x표시가 하나밖에 없습니다.
사실 x표시는 아까 세지 못한 점들로 r1 < x <= r2 경우의 (x, 0) 점들입니다.
개수는 (r2 - r1) * 4(사사분면)입니다.

아마 설명을 들어도 for문의 x의 범위가 1 <= x < r2 인지 이해가 안가시는 분이 있을 것 같습니다.
기억해야할 것은 위의 그림에서 개수를 구한 후 * 4를 하고 있다는 것입니다.
x = 0일 개수는 그림에서 y = 0 일 때의 개수 * 4하면서 포함되고 있습니다.
x가 r2인 경우도 마찬가지입니다.

https://school.programmers.co.kr/questions/47322 방법에서 x좌표를 for문으로 돌리는 아이디어를 얻었습니다.