[알고리즘]두 원 사이의 정수쌍

package org.example.알고리즘.두원사이의정수쌍;

import java.text.MessageFormat;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(2, 3));
    }
    
    public long solution(int r1, int r2) {
        if (!(1 <= r1 && r1 < r2 && r2 <= 1_000_000)) {
            throw new IllegalArgumentException(MessageFormat.format("r1은 1보다 크고 r2보다 작아야 합니다. r1: {0}, r2: {1}", r1, r2));
        }
        long answer = 0;
        Circle biggerCircle = new Circle(0, 0, r2);
        Circle smallerCircle = new Circle(0, 0, r1);
        answer += findIntegerPairs(biggerCircle, smallerCircle);
        return answer;
    }
    
    // 1사분면의 값만 구하여 4배를 해준다.
    public long findIntegerPairs(Circle bigger, Circle smaller) {
        long count = 0;
        for (int x = 1; x <= bigger.r; x++) {
            // 두 원의 방정식을 사용하여 y좌표의 최소값과 최대값을 찾음
            int y_max = (int) Math.floor(Math.sqrt(Math.pow(bigger.r, 2) - Math.pow(x, 2)));
            int y_min = (int) Math.ceil(Math.sqrt(Math.pow(smaller.r, 2) - Math.pow(x, 2)));
            // y의 범위가 유효한지 확인 (y_min이 y_max보다 작거나 같은지 확인)
            if (y_min <= y_max) {
                // 유효한 y 범위 내의 정수 점의 개수를 더함
                count += (y_max - y_min + 1);
            }
        }
        return count * 4;  // 4사분면에 대해 반복
    }
    
    public static class Circle {
        private final int x;
        private final int y;
        private final int r;
        
        public Circle(int x, int y, int r) {
            if (!(1 <= r && r <= 1_000_000)) {
                throw new IllegalArgumentException(MessageFormat.format("r은 1보다 크고 1_000_000 작아야 합니다. r: {0}", r));
            }
            this.x = x;
            this.y = y;
            this.r = r;
        }
        
    }
}

• 4분면의 값을 모두 구하니까 시간초과가 발생했습니다.

• findIntergerPairs 메서드는 1사분면만 찾아야합니다.
  • 1사분면의 x → 1 부터 끝까지 반복문을 돌면서
  1. 각 x 좌표에 대해 y 좌표의 최소값 y_min 과 최댓값 y_max 를 계산해야함
  2. y_min 은 작은 원의 외부, y_max 는 큰 원의 내부에 있어야함.
     1. 그렇기에 r^2= x^2 + y^2 에 근거하여

     int y_max = (int) Math.floor(Math.sqrt(Math.pow(bigger.r, 2) - Math.pow(x, 2)));
     int y_min = (int) Math.ceil(Math.sqrt(Math.pow(smaller.r, 2) - Math.pow(x, 2)));

     • Math.floor 로 최댓값은 정수값으로 내림
     • Math.ceil 로 최솟값은 정수값으로 올림

       처리를 합니다.

  3. 유효한 좌표범위안이라면 max 와 min 사이의 유효한 y좌표갯수 만큼 count 에 값을 더합니다.

Uploaded by N2T