[Algorithm][JS] 프로그래머스 - 두 원 사이의 정수 쌍
문제 설명
x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return 하도록 solution 함수를 완성해 주세요.
※ 각 원 위의 점도 포함하여 셉니다.
문제 풀이
💡 힌트
- 원의 방정식 x^2 + y^2 = r^2
- 1 사분면만 계산 후 * 4
◎ 도전 1
처음 생각한 방법은 아래와 같았습니다.
x, y 축을 반복문을 돌면서 x^2 + y^2 이 r1^2 보다 같거나 크고 r2^2 보다 같거나 작으면 count 증가
function solution(r1, r2) {
let count = 0;
for (let x = 1; x < r2; x++) {
for (let y = 0; y < r2; y++) {
let dot = x ** 2 + y ** 2;
if (r1 ** 2 <= dot && dot <= r2 ** 2) {
count++;
}
}
}
return count * 4 + 4;
}풀이법은 맞지만, 이중 반복문이다 보니 O(n^2)으로 인해 7~10 테스트 케이스에서 시간초과가 발생했습니다.
◎ 도전 2
기존 풀이 보다 더 빠른 알고리즘을 이용했어야 했습니다. 그래서 반복문 하나로만 해결할 수는 없을까 생각해 보았습니다. 해결 방법은 생각보다 간단했습니다. 두 원 사이의 Y축의 높이만 더하면 됩니다.
X축을 돌면서 y축의 최대 높이(maxH) - 최소 높이(minH)를 뺀 길이을 count에 추가
그림으로 보면 다음과 같습니다. r1 = 2, r2 = 6일 때 x축을 돌면서 초록색 높이의 값만 더해주면 됩니다.
그러면 y축의 최대 높이와 최소 높이는 어떻게 구할까요?
y축의 높이는 원의 방정식을 이용해서 y = sqrt(r^2 - x^2)로 구할 수 있습니다. 최대 높이의 경우 해당 값보다 작거나 같아야 하기 때문에 버림을 사용하고, 최소 높이의 경우 해당 값보다 크거나 같아야 하므로 올림을 해줍니다. 그리고 최소 높이의 경우 x 가 r1 보다 커지는 경우 마이너스가 되어 NaN 값이 나오게 되므로 음수가 되는 경우 0이 되도록 해줍니다.
이를 코드로 작성하면 다음과 같습니다.
function solution(r1, r2) {
let count = 0;
for (let x = 1; x <= r2; x++) {
const maxH = Math.floor(Math.sqrt(r2 ** 2 - x ** 2));
const minH = Math.ceil(Math.sqrt(r1 ** 2 - x ** 2)) || 0;
count += maxH - minH + 1;
}
return count * 4;
}이렇게 되면, 시간복잡도가 O(n)이 되므로 모든 테스트에서 성공하게 됩니다. 🎉
- 걸린 시간 : 2시간
- Y 축의 길이만 계산하면 된다는 방법을 찾아내는데 오래 걸렸다 :(