[JS] 두 원 사이의 정수 쌍

문제

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

프로그래머스

 

 

풀이

이 문제는 수학 문제다.

 

첫 번째 풀이를 진행할 때 이중 for문을 이용해 x, y 좌표별 범위 내에 있는지 검증하며 풀이를 답을 도출하는 접근법으로 풀이했는데, 제한 조건을 보면 입력이 백만까지 이므로 시간 초과 에러가 발생했다. 어찌 보면 당연한 결과였다.

 

그래서 수학의 원의 방정식을 이용했다.

원의 방정식을 이용해 x좌표별 범위에 들어올 수 있는 y좌표의 최대값과 최소값을 구했다.

 

문제에서는 원의 중점이 (0, 0) 이기 때문에 원의 방정식은 x^2 + y^2 = r^2 이다. 이 때 우리가 구해야할 y좌표를 구하려면 r^2 - x^2 = y^2 r 과 같은 유도식이 완성된다.

 

주의할 점이 두 가지 있다. 첫 번째는 x좌표의 시작이 0부터가 아닌 1부터 여야하는 점이다. 이는 1사 분면만 구한뒤 나머지 3개 분면의 경우도 모두 구하지 않고 1사분면에서 구한 값 * 4 하여 답을 도출하기 위함이다. 두 번 째는 y의 최대값과 최소값을 구한다면 각각 내림, 올림 동작을 해줘야 한다는 점이다. 이 문제에서는 두 원의 사이 영역에 들어오는 정수 값을 구하기 때문이다.

 

코드

function solution(r1, r2) {
  let answer = 0;
  for (let i = 1; i <= r2; i++) {
    const max = Math.floor(Math.sqrt(Math.pow(r2, 2) - Math.pow(i, 2)));
    const min = i < r1 ? Math.ceil(Math.sqrt(Math.pow(r1, 2) - Math.pow(i, 2))) : 0;
    answer += max - min + 1;
  }
  return answer * 4;
}