[프로그래머스 / Java] - 두 원 사이의 정수 쌍

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

 

정답 설명

해당 문제는 간단한 수학 문제입니다.

각 원의 반지름 길이는 최대 1,000,000으로, 완전 탐색을 시도하면 높은 확률로 시간 초과가 발생합니다.

우리에게 필요한 것은 점의 개수 이므로 빠른 시간 내에 점의 개수를 구하기 위한 방법들을 생각해 봅시다.

 

가장 먼저, 두 원의 중심은 항상 원점입니다. 때문에 문제에서 설명하는 범위에 포함되는 점은 1사분면 ~ 4사분면에 모두 대칭적으로 존재합니다. 이를 활용하여 우리는 하나의 사분면 위에 위치한 점의 개수만 구한 이후, 4를 곱해 원하는 결과를 얻을 수 있습니다.

 

또, 각 점의 반지름이 주어졌고 점의 좌표들을 사용해야 하기 때문에 피타고라스의 정리를 사용하면 좋습니다. y좌표를 1부터 r2의 반지름 길이까지 탐색하며 각 y 좌표에서 주어진 범위에 포함되는 점의 개수를 구하는 과정으로 점의 개수를 구할 수 있습니다. 또, 각 y 좌표에서 주어진 범위에 포함되는 점의 개수는 범위에 포함될 수 있는 점의 x 좌표 값의 범위 시작 값과 끝 값을 계산하여 구할 수 있습니다.

 

주어진 y 좌표 i에 대하여 범위에 포함되는 점의 x 좌표 범위의 시작 값 start와 end는 다음의 수식을 만족합니다.

 

$$\text{start}^2 + \text{i}^2 \geq  \text{r1}^2$$

$$\text{end}^2 + \text{i}^2 \leq \text{r2}^2$$

 

$\text{i}^2$를 이항 시키고, 양 변에 루트를 취해 다음의 수식을 얻을 수 있습니다.

$$\text{start}\geq \sqrt{\text{r1}^2-\text{i}^2}$$

$$\text{end}\leq \sqrt{\text{r2}^2-\text{i}^2}$$

 

소스 코드

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        for(int i = r2; i>0; i--){
            int startX = (int)Math.ceil(Math.sqrt(((long)r1 * r1 - (long)i*i)));
            int endX = (int)Math.floor(Math.sqrt(((long)r2 * r2 - (long)i*i)));
            answer += (endX - startX) + 1;
        }
        
        return answer*4;
    }
}

 

반성

int -> long 타입으로의 변환에서 int 끼리의 계산을 모두 수행한 이후 형 변환을 하게 되면 이미 오버플로우가 발생해 제대로 된 값을 얻을 수 없다.

형 변환의 위치를 주의하자.

//잘못된 코드
(long)(r1 * r1)
//올바른 코드
(long)r1 * r1