문제설명

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

---

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

---

입출력 예

r1	r2	result
2	3	20

---

입출력 예 설명

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

설계 과정

• 이번 문제는 그림에 나와있는 점에 어떤 기준으로 찍혀있는지 봐보자.
  또한 아래 과정은 제 1사분면 만을 구한다. 나머지 사분면들도 똑같기 때문에 이후에 *4를 해주기 위함이다.
  1부터 r2까지 돌면서 아래과정 시행 (값은 x로)

1. x 기준에서 r2만큼 떨어진 y좌표를 구함 -> 이 좌표는 내림이 되어야 한다. -> 큰 값은 쓰지 않기 때문
2. x 기준에서 r1만큼 떨어진 y좌표를 구함 -> 이 좌표는 올림이 되어야 한다. -> 작은 값은 쓰지 않기 때문
   -> 이것은 만약 r1의 길이를 넘어서는 경우가 있는데 이때는 0으로 해준다.
3. 마지막에 answer+= (두개 구한 값의 차) +1;
4. 순회를 다했다면 answer*4를 리턴

정답 코드

function solution(r1, r2) {
    var answer = 0;
    for(var x = 1;x<=r2;x++){
        var maxY = Math.floor(Math.sqrt(r2**2 - x**2));
        if(r1>x){
            var minY = Math.ceil(Math.sqrt(r1**2 - x**2));
        }
        else{
            var minY = 0;
        }
        answer+= (maxY - minY + 1);
    }
    return answer*4;
}

결과

이번 문제에 핵심은 O(n)타임으로 끝내는 것이다. 사실 구현하기 쉬운 방법으로 모든점에 대해 거리를 구하면 답은 나오겠지만 2단계인 만큼 시간복잡도를 효율적으로 구현하는 코드가 필요하다.