[Programmers] 프로그래머스 Lv.2 두 원 사이의 정수 쌍 문제풀이(C++)

 

처음엔 모든 점을 조사하는 것으로 생각했으나, 시간초과 발생

-> x좌표만 순회하며, 각각 r1에서의 y좌표, r2에서의 y좌표를 통해 길이를 구한 후 점 개수에 반영하는 형태로 변경

-> 수행시간이 O(n^2) 에서 O(n)으로 감소

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;
/*
<문제>
중심이 원점인 두 원 사이의 정수좌표 점 개수 구하기(원 위의 점 포함)
r1 < r2 <= 100만
 
<풀이>
하나의 사분면에서 적용
 
x좌표 1~r2-1까지 반복
  root_y2_1 = |x^2 - r1^2| ^ (1/2) + 1 -> x값에 대한 r1 원 위의 y좌표(시작)
  root_y2_2 = |x^2 - r2^2| ^ (1/2) -> x값에 대한 r2 원 위의 y좌표(끝)
  answer += root_y2_2 - root_y2_1 + 1
 
answer *= 4; //사분면 처리
answer += (r2-r1+1)*4   //x, y축 위의 점 처리
 
 
*/
 
long long solution(int r1, int r2) {
    long long answer = 0;
 
    for (int i = 1; i <= r2 - 1; i++)   //i : x좌표
    {
        int root_y2_1;
        if(i<r1) {
            double tmp = sqrt((long long)r1*r1 - (long long)i*i); //절댓값 처리
            if(tmp - (int)tmp == 0)  //정수로 딱 맞아떨어지는 경우
                root_y2_1 = (int)tmp;
            else root_y2_1 = (int)tmp+1;
        }
        else root_y2_1 = 1;
        int root_y2_2 = sqrt( (long long)r2*r2 - (long long)i*i ); //x값에 대한 r2 원 위의 y좌표(끝)
 
        answer += root_y2_2 - root_y2_1 + 1;    //가능한 y좌표 수 더하기
    }
    answer *= 4; //사분면 처리  
    answer += ((r2 - r1 + 1) * 4);   //x, y축 위의 점 처리
 
    return answer;
}