[프로그래머스 Level.2] 두 원 사이의 정수 쌍 (연습문제) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/181187#

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 두 원 사이의 정수 쌍

 

 

문제 설명

 

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다.

반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.

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

 

---

 

제한 사항

 

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

 

---

 

입출력 예

 

r1	r2	result
2	3	20

 

---

 

입출력 예 설명

 

 

 

 

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

 

 

 

 

 

 

나의 코드

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        // 각 원의 넓이
        long areaR1 = (long) Math.pow(r1, 2);
        long areaR2 = (long) Math.pow(r2, 2);
        
        for(int x=0; x<r2; x++) {
            // y = 루트(r^2 - x^2)
            // x에 따라 테두리 포함 원의 내부에 있는 가장 큰 정수 y좌표
            long maxY2 = (long) Math.sqrt(areaR2 - (long) Math.pow(x, 2));
            long maxY1 = (long) Math.sqrt(areaR1 - (long) Math.pow(x, 2));
            
            // 0 <= x < r2 까지 구했으므로 *4 해주면 r2 원의 테두리 + r1 과 r2 사이 내부의 모든 점들이 된다.
            answer += (maxY2 - maxY1) * 4;
            
            // r1 테두리 점들을 구해 더해준다. maxY1이 정수이면 작은 원의 테두리의 점이므로 포함시켜야 한다.
            // 0 <= x < r1 까지 구했으므로 *4 해주면 r1 원의 테두리의 모든 점들이 된다.
            if(x < r1 && Math.sqrt((areaR1 - Math.pow(x, 2))) % 1 == 0) answer += 4;
        }
        
        return answer;
    }
}

 

풀이

1. r1 원의 테두리에 해당하는 점들과 r1 원과 r2 원의 사이에 해당하는 점과 r2 원의 테두리에 해당하는 점들을 모두 구해야 하는 문제이다.
2. x^2 + y^2 = r^2을 이용하여 x를 0부터 r 전까지 순회하면서 각 x마다 가능한 y 좌표의 개수를 구한다. 
3. 각 x마다 y좌표 최대는 루트(r^2 - x^2) 이고 y좌표 최대를 내림차순하여 정수로 변경하면 가능한 정수 y좌표의 개수가 된다. (수가 클 수 있으므로 int형이 아닌 long형으로 변환하는 것에 주의한다.)
4. 예를 들어 r=3일 때 x는 0부터 2까지 순회하며 x=0일 때 y좌표 최대는 3.0, y좌표 최대는 2.828... , x=1일 때 y좌표 최대는 2.236... 이고 따라서 소숫점을 날리면 x=0일 때 가능한 y좌표는 3개, x=1일 때 가능한 y좌표는 2개, x=2일 때 가능한 y좌표는 2개가 된다.
5. 이렇게 구한 좌표들을 *4 하면 반지름 r의 모든 점들을 구할 수 있다. (시계 or 반시계 방향으로 한바퀴 돌리면 각 4분면에 모든 좌표들이 찍히는 것과 같다.)
6. 이렇게 r2로 가능한 모든 좌표들을 구하여 r1으로 가능한 모든 좌표들을 구해 빼주면 r1의 테두리에 속하는 점들을 제외한 r1 원과 r2 원 사이의 점들과 r2 테두리에 속하는 점들이 된다.
7. 따라서 r1 테두리에 속하는 점들을 구하여 더해주면 된다.
8. 해당 점들을 구하는 방법도 x를 0부터 r1 전까지 순회하면서 y좌표 최대를 구했을 때 해당 y좌표 최대가 정수인 것들의 개수를 구하여 *4 해서 더해주면 된다.