두 원 사이의 정수 쌍 [자바]

 

🧫 문제 분석

✔️ 출처

두 원 사이의 정수 쌍 level 2

📖 문제

 

많이 틀렸고, 질문도 보면서 참고하면서 풀었다. 

 

처음에는 규칙이 있나 해서 규칙을 찾아서 해봤는데 그건 작은 값이였을때만이여서 의미 없었고,

임의의 좌표를 생성하고 그 좌표까지의 거리가 r1보다 크면서 r2 보다 작은 것을 찾는 방식을 했는데 

당연히 O(n^2) 라서 안된다. 

 

 

핵심은 두원의 특정 x값일 때 두 원의 y값 사이를 구하는 것이다. (혹은 특정 y값일 대 두원 사이의 x값)

 

 

중요한 것은 r2의 경우 r2의 y값을 내림처리하고

r1의 y값을 올림 처리해야한다. 

 

x =1 일때 뿐만 아니라 그외에도 원의 방정식에서 x값을 넣어 구한 해당 원의 y값은 

x = 0, y = 0 일때를 제외하고는 해당 원의 반지름보다 작다.

 

r2를 내리고, r1을 올린 후 + 1한 값이 두 값을 뺀 것이 바로 정수의 개수이다. 

 

 

따라서 필자는 x= 0를 제외하고, 1사분면에 있는 정수들을 찾고, 

4를 곱한다. 그리고 x = 0 일때와 y = 0 일때를 구한다. 

 

(r2 - r1 + 1) * 4 가 4방향의 x = 0일때와 y = 0일때의 값이다. 

 

---

🔅 문제 풀이

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        long r1Length = (long)r1 * r1;
        long r2Length = (long)r2 * r2;
        // x값에 따른 두 원의 y값 구하기 
        for(int x = 1; x < r2; x++) {
            int r1y = (int)Math.ceil(Math.sqrt(r1Length - (long)x * x));
            int r2y = (int)Math.floor(Math.sqrt(r2Length - (long)x * x));
			
            // 0인 부분은 제외하고 구한다. (수직, 수평 부분은 따로 계산할 예정)
            r1y = (r1y == 0) ? 1 : r1y;
            answer += r2y - r1y + 1; // 정수 쌍 
        }
        
        // r2 - r1 + 1 이 수직, 수평에 있는 정수 쌍의 개수 
        return answer * 4 + (r2 - r1 + 1) * 4;
    }
}

 

🔅 리팩토링

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        long r1Length = (long)r1 * r1;
        long r2Length = (long)r2 * r2;
        
        // x값에 따른 두 원의 y값 구하기 
        for(int x = 1; x <= r2; x++) {
            int r1y = (int)Math.ceil(Math.sqrt(r1Length - (long)x * x));
            int r2y = (int)Math.floor(Math.sqrt(r2Length - (long)x * x));
			
            answer += r2y - r1y + 1; // 정수 쌍 
        }
        
        return answer * 4;
    }
}

굳이 무조건 1부터 구하고 수직, 수평일때를 따로 구할 필요가 없었다. x가 r2일때까지 구하면서 

r1y가 0이여도 구하면 x = 0일때 정수 쌍을 제외한 1사분면의 모든 정수쌍을 구할 수 있기에 

*4를 해주면 된다. 

❗ 오답노트 / 필요한 지식

1. 삽질을 많이했다. 알고리즘은 항상 효율적인 방법이 있다.