[프로그래머스] [python / Java] 2단계 : 두 원 사이의 정수 쌍

기존 코드

def solution(r1, r2):
    answer = 0
    sum = 0
    for i in range(1, r2 + 1):  # x 좌표: 1 ~ r2
        for j in range(0, r2 + 1):  # y 좌표: 0 ~ r2
            distance_squared = i**2 + j**2
            if r1**2 <= distance_squared <= r2**2:
                sum += 1
    answer = sum * 4
    return answer

모든 x와 y좌표의 거리가 r1과 r2 사이에 있는지 검사하는 코드이다.

1사분면의 좌표들만 구해 *4를 하는 방향으로 코드를 개선하였다.

하지만 이마저도 코드 실행 시간이 너무 오래걸려 개선이 필요하였다.

 

정답 코드 python

import math

def solution(r1, r2):
    answer = 0
    for x in range(1, r2 + 1):  # x 좌표: 1 ~ r2
        max_y = int(math.sqrt(r2**2 - x**2))  # 큰 원의 경계 안쪽 최대 y 좌표
        min_y = int(math.ceil(math.sqrt(r1**2 - x**2))) if r1**2 - x**2 > 0 else 0  # 작은 원 경계 바깥 최소 y 좌표
        answer += max_y - min_y + 1  # 해당 x에서 y 좌표 개수 누적
    answer *= 4
    return answer

gpt의 도움을 받아 작성한 코드이다.

math module을 이용해 1사분면에서 큰 원의 경계 안쪽 최대 y 좌표와 작은 원 경계 바깥 최소 y좌표를 구한다.

이렇게 구한 좌표값들로 개수를 누적시켜 구한다. 기존의 거리 계산과는 접근이 다른 방식이다.

정답 코드 java

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

        for (int x = 1; x <= r2; x++) {  // x 좌표: 1 ~ r2
            // 큰 원의 경계 안쪽 최대 y 좌표
            int max_y = (int) Math.floor(Math.sqrt((long)r2 * r2 - (long)x * x));

            // 작은 원의 경계 바깥 최소 y 좌표
            int min_y = (int) Math.ceil(Math.sqrt((long)r1 * r1 - (long)x * x));

            // 해당 x에서 가능한 y 좌표 개수 누적
            answer += (max_y - min_y + 1);
        }

        // 대칭성을 고려하여 4배 계산
        return answer *= 4;
    }
}