catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 두 원 사이의 정수 쌍

jin@catsriding.com
Oct 23, 2024
Published byJin
999
프로그래머스 | Level 2 | 두 원 사이의 정수 쌍

Programmers | Level 2 | 두 원 사이의 정수 쌍

Problems

󰧭 Description

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

programmers-level2-integer-coordinate-between-circles_00.png

※ 각 원 위의 점도 포함하여 셉니다.

 Constraints

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

󰦕 Examples

r1r2result
2320

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public long solution(int r1, int r2) {
        long points = 0;  // 정수 좌표의 개수를 저장할 변수
        for (int x = 1; x <= r2; x++) {  // x 좌표를 1부터 r2까지 반복
            int max = findMax(r2, x);  // 외곽 원에서 주어진 x 좌표에 대한 최대 y 값을 구함
            int min = findMin(r1, x);  // 내부 원에서 주어진 x 좌표에 대한 최소 y 값을 구함
            
            points += max - min + 1;   // 두 원 사이에 존재하는 정수 y 좌표의 개수를 누적
        }
        return points * 4;  // 1사분면의 좌표 개수를 기반으로 전체 공간에 대한 좌표 계산
    }
    
    // 외곽 원의 주어진 x 좌표에 대한 최대 y 값을 구하는 함수
    private int findMax(int radius, int x) {
        return (int) Math.floor(Math.sqrt((long) Math.pow(radius, 2) - (long) Math.pow(x, 2)));
    }
    
    // 내부 원의 주어진 x 좌표에 대한 최소 y 값을 구하는 함수
    private int findMin(int radius, int x) {
        return (int) Math.ceil(Math.sqrt((long) Math.pow(radius, 2) - (long) Math.pow(x, 2)));
    }
}

 Approaches

이 문제는 원의 방정식을 이용하여 두 원 사이의 공간에 존재하는 정수 좌표를 찾는 문제입니다. 각 원 위 또는 원 사이의 공간에 존재하는 정수 좌표는 좌표의 대칭성을 이용하여 1사분면에 대해 계산한 후, 이를 4배하여 전체 공간에서의 좌표 개수를 구하는 방식으로 풀이합니다.

1. 문제 분석

주어진 문제는 두 원 사이의 공간에 존재하는 정수 좌표의 개수를 구하는 문제입니다. 원의 방정식은 x^2 + y^2 = r^2로 표현되며, 이 방정식을 활용하여 두 원의 반지름을 기준으로 x 값을 고정하고 해당 x 값에 대응하는 y 값을 계산하여 두 원 사이의 정수 쌍을 찾습니다.

1사분면의 좌표에서 x 값을 1부터 r2까지 변하게 하면서, 외곽 원과 내부 원의 y 좌표 범위를 구합니다. 그 후, 이 범위 내의 모든 정수 좌표를 계산합니다. 문제는 대칭성을 갖고 있기 때문에 1사분면에서의 좌표 개수만 계산한 뒤, 이를 4배하여 전체 좌표 개수를 구합니다.

2. 접근 방식

두 원 사이의 공간에 존재하는 정수 좌표를 구하기 위해 다음의 단계로 문제를 해결합니다.

  1. 원의 방정식 활용: 원의 방정식을 이용해 각 x 좌표에 대응하는 y 좌표 범위를 계산합니다. 여기서 r2는 외곽 원의 반지름, r1은 내부 원의 반지름입니다.
  2. 1사분면에서 좌표 계산: x 좌표를 1부터 r2까지 증가시키면서 해당 x 값에 대해 내부 원과 외곽 원 사이에 존재하는 y 값의 범위를 구합니다. 이를 통해 해당 범위 내에서 존재하는 정수 좌표의 개수를 계산합니다.
  3. 전체 좌표 개수 계산: 대칭성을 활용해 1사분면에서 구한 좌표 개수를 4배하여 전체 공간에서의 좌표 개수를 구합니다.
3. 1사분면에서 X 좌표 범위 설정

두 원 사이의 정수 좌표를 구할 때, 먼저 1사분면에서의 x 좌표 범위를 설정합니다. x 값은 1부터 외곽 원의 반지름인 r2까지 탐색합니다. x가 0인 경우, 대칭성 때문에 다른 사분면에서 동일한 좌표가 중복 계산되므로, 이를 제외하고 x를 1부터 시작합니다. 이렇게 각 x에 대해 두 원 사이의 y 좌표 범위를 계산하고, 1사분면에서 구한 결과는 대칭성을 이용해 전체 좌표 계산에 적용할 수 있습니다.

Solution.java
long points = 0;  // 정수 좌표의 개수를 저장할 변수
for (int x = 1; x <= r2; x++) {...}  // 각 x 좌표에 대해 최대 및 최소 y 좌표 계산
4. X 좌표에 대한 최대 Y 좌표 계산

이제 주어진 x 좌표에 대해 외곽 원의 경계에서 가장 큰 y 값을 계산합니다. 이는 해당 x 값에서 원의 경계에 위치한 가장 높은 y 좌표를 의미합니다. 원의 방정식을 이용해, 주어진 x 값에 따른 y 값을 계산한 후, 이 값이 소수일 경우, 소수 부분을 버리고 가장 가까운 아래 정수로 내림 처리합니다. 내림 처리를 통해 원의 경계보다 살짝 벗어난 소수 좌표는 제외하고, 실제로 원의 내부나 경계에 해당하는 정수 좌표만을 반영하게 됩니다. 이 과정에서 구해진 값이 해당 x 좌표에서의 최대 y 좌표가 됩니다.

Solution.java
// 내부 원의 주어진 x 좌표에 대한 최대 y 값을 구하는 함수
private int findMax(int radius, int x) {
    return (int) Math.floor(Math.sqrt((long) Math.pow(radius, 2) - (long) Math.pow(x, 2)));
}
5. X 좌표에 대한 최소 Y 좌표 계산

이제 동일한 x 좌표에 대해 내부 원에서의 최소 y 값을 계산합니다. 이는 해당 x 값에서 내부 원의 경계에 위치한 가장 낮은 y 좌표를 의미합니다. 이를 구하기 위해 원의 방정식을 이용해 y 값을 계산한 후, 이 값이 소수일 경우, 소수 부분을 올림 처리하여 가장 가까운 위쪽 정수로 반올림합니다. 이렇게 함으로써, 실제로 내부 원의 경계나 그 외부에 해당하는 가장 작은 정수 좌표부터 계산이 시작되도록 합니다. 이를 통해 구해진 값이 주어진 x 좌표에서의 최소 y 좌표가 됩니다.

Solution.java
// 내부 원의 주어진 x 좌표에 대한 최소 y 값을 구하는 함수
private int findMin(int radius, int x) {
    return (int) Math.ceil(Math.sqrt((long) Math.pow(radius, 2) - (long) Math.pow(x, 2)));
}
6. X 좌표마다 정수 좌표 개수 계산

이제 각 x 좌표에 대해 두 원 사이에 존재하는 y 좌표의 범위를 확인했으므로, 그 범위 내에서 존재하는 정수 좌표의 개수를 구할 차례입니다. 외곽 원에서 계산한 가장 큰 y 좌표와 내부 원에서 계산한 가장 작은 y 좌표 사이에 얼마나 많은 정수 좌표가 있는지 계산합니다. 두 값의 차이를 구한 후, 그 사이에 포함되는 모든 정수 좌표를 더해줍니다. 이 개수를 누적하여, 1사분면에서 두 원 사이에 있는 정수 좌표의 총합을 계산하게 됩니다.

Solution.java
for (int x = 1; x <= r2; x++) {
    int max = findMax(r2, x);  // 외곽 원에서 주어진 x 좌표에 대한 최대 y 값을 구함
    int min = findMin(r1, x);  // 내부 원에서 주어진 x 좌표에 대한 최소 y 값을 구함
    
    points += max - min + 1;   // 두 원 사이에 존재하는 정수 y 좌표의 개수를 누적
}
7. 대칭성 기반으로 전체 좌표 계산 후 반환

원의 대칭성에 따라, 1사분면에서 구한 좌표 개수는 다른 3사분면에도 동일하게 적용됩니다. 따라서 1사분면에서 계산한 좌표 개수를 4배하여 전체 공간에서의 정수 좌표 개수를 구할 수 있습니다. 이렇게 대칭성을 활용함으로써 계산 속도를 크게 향상시킬 수 있습니다.

// 1사분면의 좌표 개수를 기반으로 전체 공간에 대한 좌표 계산
return points * 4;

󰄉 Complexity

  • ⏳ TC: O(n)
  • 💾 SC: O(1)

시간 복잡도는 r2에 대해 선형적으로 증가합니다. 각 x 좌표에 대해 최대 및 최소 y 좌표를 계산하는 과정에서 제곱근 연산이 발생하지만, 이 연산은 상수 시간에 이루어지므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 주어진 문제에서 추가적인 배열이나 리스트를 사용하지 않으므로 상수 공간 O(1)을 차지합니다.

  • Algorithm
  • Math