[프로그래머스][C++] 두 원 사이의 정수 쌍

두 원 사이의 정수 쌍

문제 링크

두 원 사이의 정수 쌍

분석

중심인 원점을 기준으로 반지름 r1, r2로 그려진 두 원이 있을 때, 두 원 사이에 있는 정수 좌표 쌍의 개수를 구하는 문제입니다.

특정 좌표 (x, y)가 원점으로부터 거리 d일때, $d = \sqrt{x^2 + y^2}$입니다.
이때 이 점이 두 원 사이에 존재하려 한다면 $r1^2 \leq x^2 + y^2 \leq r2^2$이 성립해야합니다.
루트를 사용하지 않고, 제곱값 비교로 처리해야 성능에 좀 더 유리하게 구현할 수 있습니다.

전체 좌표 공간 즉, 모든 (x, y)에 대해 탐색하는 것은 비효율적입니다.
x좌표에 대해서 0부터 r2까지 순회하면서, 그에 맞는 y값의 범위를 구해 세는 방식이 효율적입니다.
x값이 고정일 때, y의 최소값은 $x^2 + y^2 \geq r1^2$, 최대값은 $x^2 + y^2 \leq r2^2$입니다.
이때 y는 정수이므로, 최소값은 $y = \sqrt{r1^2 - x^2}$, 최대값은 $y = \sqrt{r2^2 - x^2}$입니다.
위 범위 안의 정수 y값 개수를 더하면 됩니다.
또한 제 1사분면에 있는 점을 구한 뒤, 대칭을 이용해서 전체 사분면의 점 개수를 유추할 수 있습니다.

다음과 같은 로직을 구성하면 됩니다.

1. 반복문으로 x좌표를 1부터 r2까지 반복합니다.
2. 각 x에 대해 가능한 y범위를 계산하고, 누적합니다.
3. 반복문이 끝났고, 제1사분면을 기준으로 값을 구했다면, 4배 해줍니다.

$x^2$과 $y^2$처럼 제곱 연산 시 int 범위를 초과하는 오버플로우가 발생할 수 있습니다.
sqrt함수는 부동소수점 오차가 있으므로 주의해야합니다.
올림과 내림은 ceil, floor함수를 사용할 수 있지만, 형변환과 정수 처리에 주의할 필요가 있습니다.

올림을 하는 이유는 y의 최소값을 구하는 루트 계산 결과가 2.3일 경우, 문제에서는 y = 2라는 조건을 만족할 수 없습니다.
즉, 최소 y는 3이어야 하기 때문에 올림합니다.
내림을 하는 이유는 y의 최대값을 구하는 루트 계산 결과가 5.8일 경우, 문제에서는 y = 6이라는 조건을 만족할 수 없습니다.
즉, 최대 y는 5여야 하기 때문에 내림합니다.

풀이

#include <cmath>

using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0;
    
    // x를 고정하고, 가능한 y의 개수를 구하는 반복문
    for (int x = 1; x <= r2; ++x)
    {
        // x^2을 long long 자료형으로 미리 계산
        long long xSquared = (long long)x * x;
        
        // y의 최대값 y^2 ≤ r2^2 - x^2
        long long maxY = (long long)floor(sqrt((long long)r2 * r2 - xSquared));
        
        // y의 최소값 y^2 ≥ r1^2 - x^2
        // r1^2 - x^2이 음수인 경우는 조건을 만족하는 y가 없기 때문에 0으로 유지
        long long minY = 0;
        if (xSquared < (long long)r1 * r1)
        {
            minY = (long long)ceil(sqrt((long long)r1 * r1 - xSquared));
        }
        
        if (maxY >= minY)
        {
            // maxY - minY + 1이 해당 x에서 가능한 y의 개수
            answer += maxY - minY + 1;
        }
    }
    
    // 현재까지 센 점들은 x > 0, y ≥ 0 범위의 제1사분면 상의 점이므로 전체 사분면을 반영
    answer *= 4;
    
    return answer;
}

성능 요약

시간 복잡도는 $O(r2)$입니다.

• x를 고정하고, 가능한 y의 개수를 구하는 반복문 $O(r2)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉통과 (0.01ms, 4.2MB)
테스트 2 〉통과 (0.01ms, 4.21MB)
테스트 3 〉통과 (0.01ms, 3.63MB)
테스트 4 〉통과 (0.01ms, 4.21MB)
테스트 5 〉통과 (0.01ms, 4.2MB)
테스트 6 〉통과 (0.02ms, 4.15MB)
테스트 7 〉통과 (2.49ms, 4.14MB)
테스트 8 〉통과 (4.21ms, 4.22MB)
테스트 9 〉통과 (1.87ms, 4.16MB)
테스트 10 〉통과 (2.87ms, 4.15MB)