[Programmers] 두 원 사이의 정수 쌍 ( 좌표 )

- 목차

 

 

문제 설명.

https://school.programmers.co.kr/learn/courses/30/lessons/181187?language=java

프로그래머스

 

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

 

입출력 예 설명

 

 

문제 분석.

좌표의 정수 쌍들의 갯수를 조회합니다.

만약 모든 x, y 좌표를 모두 탐색하게 되면 시간 복잡도의 문제를 겪게 됩니다.

그래서 정해진 반지름 r 내부에 존재하는 정수쌍을 찾는 함수를 만들어 시간복잡도를 최소화시켜야합니다.

 

아래와 같은 방식으로 반지금 r 내부에 존재하는 정수쌍의 갯수를 구할 수 있습니다.

그리고 반지름의 border 를 포함하는지 아닌지에 따라서 결과가 달리지므로 개구간 또는 폐구간에 대한 확인 절차 또한 중요합니다.

  long count (int r, boolean closed) {
    long result = 0;
    double rr = Math.pow(r, 2);
    for (int i = 1; i < r; i++) {
      double ii = Math.pow(i, 2);
      double distance = Math.sqrt(rr - ii);
      long intDist = (long) distance + 1;
      if ( !closed && Math.floor(distance) == distance)
        intDist--;
      result += (intDist);
    }
    if (closed) result++;
    return result * 4 + 1;
  }

 

 

문제 풀이.

class Solution {
  public long solution(int r1, int r2) {
    long answer = 0;
    answer = count(r2, true);
    long r1Count = count(r1, false);
    answer = answer - r1Count;
    return answer;
  }

  long count (int r, boolean closed) {
    long result = 0;
    double rr = Math.pow(r, 2);
    for (int i = 1; i < r; i++) {
      double ii = Math.pow(i, 2);
      double distance = Math.sqrt(rr - ii);
      long intDist = (long) distance + 1;
      if ( !closed && Math.floor(distance) == distance)
        intDist--;
      result += (intDist);
    }
    if (closed) result++;
    return result * 4 + 1;
  }
}