[Programmers] 두 원 사이의 정수 쌍

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

프로그래머스

 

Solution

두 원 사이에 존재하는 정수 좌표를 가진 점의 개수를 구하는 문제입니다.

피타고라스의 정리를 이해하면 문제를 조금 더 쉽게 이해할 수 있습니다.

 

우선 한 원 안에 있는 정수 좌표 점의 개수를 구하는 방식은 다음과 같습니다.

function getCircleDot(r){
    let cnt = 0;
    for(let y=-r; y<= r; y++){
        let y_ = Math.abs(y); //y좌표는 절대값으로 계산합니다.
        const x = Math.pow(Math.pow(r, 2) - Math.pow(y_, 2), 0.5); //피타고라스의 정리에 따른 x좌표 계산
        cnt+= Math.floor(x) + 1;
    }
    return cnt * 2 - r*2 - 1; //중복된 점의 개수를 제거
}

y 좌표에 따른 x좌표를 구하고 그 x좌표까지의 점 개수를 세면 됩니다.

 

이 알고리즘을 적용해 위 문제를 풀 수 있습니다.

y좌표에 따른 r2_x 좌표(반지름 r2를 가진 원의 x좌표)와 r1_x 좌표를 구한 뒤 그 좌표 사이에 있는 정수 좌표의 개수를 세어주면 됩니다.

다만 r2_x 좌표는 내림처리를, r1_x 좌표는 올림처리를 해줘야 합니다. 그래야 그 사이에 있는 정수좌표의 개수를 구할 수 있습니다.

 

전체코드

function solution(r1, r2) {
    let cnt = 0;
    for (let y=-r2; y<=r2; y++){
        let y_ = Math.abs(y);
        let r2x = Math.pow(Math.pow(r2, 2) - Math.pow(y_, 2), 0.5);
        let r1x = y_ > r1 ? 0 : Math.pow(Math.pow(r1, 2) - Math.pow(y_, 2), 0.5);
        cnt+= Math.floor(r2x) - Math.ceil(r1x) + 1; //r2_x는 내림처리, r1_x는 올림처리
    }
    return cnt * 2 - (r2-r1+1)*2; //중복된 점의 개수 제거
    
}