두 원 사이의 정수 쌍

링크

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

문제

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

※ 각 원 위의 점도 포함하여 셉니다.

문제 풀이

겹쳐지는 서로 다른 크기의 두 원에서 겹쳐지지 않는 정수쌍 좌표들의 개수에 대해서 구하는 문제이다.

이 문제는 좌표는 사분면으로 나누어져 있다는 것과 피타고라스의 정리를 활용해서 각각의 x 좌표에 대해서 대응되는 y 좌표보다 작거나 같은 정수를 구하면 된다.

즉 x 좌표를 증가시켜나가며 그에 대응 되는 정수 y 좌표의 개수를 구하면 되는 방식이다.

시간복잡도를 고려하여 r1과 r2에 대해서 모두 1사분면만 구하여 4배를 하는 방식으로 구한다.

r1에 대해서 1사분면의 점의 개수를 구하고, r2에 대해서 1사분면의 점의 개수를 구한 뒤에 둘을 빼는 것으로 1사분면의 점의 개수를 구한다. 거기에 *4를 해서 전체 사분면의 점의 개수를 구할 수 있다.

주의할 점으로는 작은 원에서 원의 경계에 해당하는 부분은 답을 반환할 때 포함시켜야하기 때문에 해당 부분에 대해서만 따로 처리를 해줄 수 있도록 코드를 작성한다.

사분면을 제외하고 x축, y축에 위치하는 점에 대해서도 셈을 한 뒤에 각각의 점들을 모두 더해서 값을 반환하도록 한다.

코드

// 1. r1 < r2 => 원의 반지름
// 2. 두 원이 겹치지 않는 부분에 위치한 (x, y)의 개수 -> 단 x, y는 정수

// 좌표에서 1사분면에서 나오는 좌표의 개수만 계산하고 *4를 진행해서 전체 좌표의 개수를 구한다.
// 최대 백만이 제한 -> 일일히 구해도 시간초과x
// 원의 반지름을 알고 있으므로 정수 x 좌표에 대해서 나올 수 있는 y 값을 구하고 그 아래의 정수의 개수를 구한다.
// x, y 좌표 축에 대해서는 따로 마지막에 합산하도록 한다.

function solution(r1, r2) {
    let small = 0
    let big = 0
    let smallEdge = 0
    
    const r1Pow = r1 ** 2
    const r2Pow = r2 ** 2
    
    // 작은 원
    for(let x = 1; x < r1; x++) {
        // 피타고라스 활용해서 정수 x에 대한 실수 y 구하기
        const y = Math.sqrt(r1Pow - x ** 2)
        // y에 대해 내림한 값을 결과에 더함
        small += Math.floor(y)
        // 작은 원의 경계 부분은 따로 개수를 계산
        if(y%1 === 0) smallEdge++
    }
    
    // 큰 원
    for(let x = 1; x < r2; x++) {
        // 피타고라스 활용해서 정수 x에 대한 실수 y 구하기
        const y = Math.sqrt(r2Pow - x ** 2)
        // y에 대해 내림한 값을 결과에 더함
        big += Math.floor(y)
    }
    
    // 1사분면 = big - small + smallEdge
    // 네 개의 사분면 = 4 * (big - small)
    // x축, y축 = (r2 - r1) * 4 + 4 
    //    => 큰 원의 반지름에서 작은 원의 반지름을 빼면 원점에서 하나의 축을 얻을 수 있는데 작은 원의 경계도 답에 포함되므로 +4
   
    return 4 * (big - small + smallEdge) + (r2 - r1) * 4 + 4 
}