[프로그래머스] 두 원 사이의 정수 쌍 | Java - 민민의 하드디스크 - 티스토리

두 원 사이의 정수 쌍

문제 설명

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

 

제한 사항

1 ≤ r1 < r2 ≤ 1,000,000

입출력 예

입출력 예 설명

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

코드 1

class Solution {
    public int solution(int r1, int r2) {
        int answer = 0;
        for (int x = -r2; x <= r2; x++) {
            for (int y = -r2; y <= r2; y++) {
                if (x*x + y*y >= r1*r1 && x*x + y*y <= r2*r2) {
                    answer++;
                }
            }
        }
        return answer;
    }
}

결과

시간 초과 (2중 for문에 음수부터 양수까지의 모든 값을 돌아서 그런 것 같음.)

그래서 for문의 시작을 -r2가 아닌 0으로 시작하여 2배만큼 곱해줘야겠다 생각함.

하지만 아무리 수정해도 테스트7~10까지의 늪에서 벗어나지 못 함.
그래서 그냥 확인해봤다.

다른 사람의 코드

728x90

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

        for (int i = 1; i <= r2; i++) {
            int start = (int) Math.ceil(Math.sqrt((long) r1 * r1 - (long) i * i));
            int end = (int) Math.floor(Math.sqrt((long) r2 * r2 - (long) i * i));

            answer += end - start + 1;
        }

        return answer * 4;
    }
}

생각보다 간단했구나..라는 생각이 드네

결과