프로그래머스 두 원 사이의 정수 쌍 자바 풀이

문제 링크

문제 요약

원점이 중심인 두 원이 있고 반지름은 각각 r1, r2다 (r1 < r2)
두 원 사이 공간에서 x, y 좌표가 모두 정수인 점의 개수를 구하는 문제다
원 위의 점도 포함해서 센다

문제 풀이

처음에는 x, y 좌표를 이중 for문으로 전부 돌면서 각 점이 두 원 사이에 있는지 판별하면 되겠다고 생각했다.

하지만 r2가 최대 1,000,000이라 x, y 범위도 그만큼 커지는데, 좌표 평면 전체를 다 훑으면 O(r2²)라 시간 안에 절대 끝나지 않는다.

이 문제의 핵심은 두 원이 원점 대칭이므로 1사분면에서만 점의 개수를 세고 4를 곱하면 된다는 점이다.

x를 1부터 r2까지 하나씩 늘려가면서, 그 x에서 세로로 들어갈 수 있는 y의 범위를 구한다
큰 원 안에 들어가는 y의 최댓값은 sqrt(r2^2 - x^2)를 내림한 값이다
x가 작은 원의 반지름 r1보다 작을 때는, 작은 원 밖으로 나가는 최소 y가 sqrt(r1^2 - x^2)를 올림한 값이어야 한다
x가 r1 이상이면 그 세로줄은 어떤 y를 잡아도 이미 작은 원 밖이므로 y=0부터 셀 수 있다
각 x마다 maxY - minY + 1만큼을 더해서 1사분면의 점 개수를 구하고, 마지막에 4를 곱한다

최종 코드

java

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;

        long r1Square = (long) r1 * r1;
        long r2Square = (long) r2 * r2;

        // 1사분면에서 x를 하나씩 늘려가며 세로줄에 들어갈 y 범위를 구한다
        for (long x = 1; x <= r2; x++) {
            long maxY = (long) Math.floor(
                Math.sqrt(r2Square - x * x)
            ); // 큰 원 안에 들어가는 y의 최댓값

            long minY;

            if (x < r1) {
                minY = (long) Math.ceil(
                    Math.sqrt(r1Square - x * x)
                ); // 작은 원 밖으로 나가는 최소 y
            } else {
                minY = 0; // x가 r1 이상이면 이미 작은 원 밖이므로 y=0부터 셀 수 있다
            }

            answer += maxY - minY + 1;
        }

        return answer * 4; // 나머지 3개 사분면도 대칭이므로 4를 곱한다
    }
}

두 원 사이의 정수 쌍

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기