CODEKATA 129 ~ 130

129번 우박수열 정적분

/*
문제 분석
1. 정보
    - 콜라츠 추측이란 로타르 콜라츠가 제기한 추측으로 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측
    - 규칙은 다음과 같음
        - 1. 입력된 수가 짝수라면 2로 나눔
        - 1. 입력된 수가 홀수라면 3을 곱하고 1을 더함
        - 2. 결과로 나온 수가 1보다 크다면 1번 작업을 반복
    - 은지는 콜라즈 추측(우박수열)을 좌표 평면 위에 꺾은선 그래프로 나타내 보려고 함
    - 초항이 k인 우박수열이 있다면, x = 0 일때 y = k이고 다음 우박수는 x = 1에 표시함.
    - 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 직선으로 연결하여 꺾은선 그래프를 만들음.
    - 또한 은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶음
    - x에 대한 어떤 범위 [a,b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0으로 둘러 쌓인 공간의 면적과 같음
    - 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에서 정적분을 해보려고 함.
    - 0 이상의 수 b에 대해 [a, -b] 에 대한 정적분 결과는 x = a, x = n -b, y = 0으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미

2. 목표
    - 우박수의 초항 k와 정적분을 구하는 구간들의 목록 ranges가 주어질 때 결과 목록을 return
    
3. 제약 조건
    - 2 <= k <= 10000
    - 1 <= ranges <= 10000
        - range의 원소는 [a,b] 형식이며 0 <= a < 200, -200 < b <= 0
    - 모든 입력에 대해 정적분의 결과는 2^27을 넘지 않음
    

풀이
1. 아이디어
    - 일단 정적분을 하기 위해선 우박수열을 구해야 함
    - 따라서 k가 규칙을 통한 과정을 거쳐 1이 될때까지 좌표 값을 구함
    - 좌표값을 구한 이후
        - 0부터 200까지의 각 (i, i + 1)에 해당하는 크기를 구하여 갑을 저장
        - ranges 배열을 돌면서
            - a ~ n - b까지의 크기를 result배열에 저장
*/

import java.util.ArrayList;
import java.util.List;

class Solution {

        List<Integer> collatz = new ArrayList<>();
        double[] size;

        public double[] solution(int k, int[][] ranges) {
            getCollatz(k);
            size = new double[collatz.size()];
            getSize();
            double[] answer = new double[ranges.length];

            for (int i = 0; i < ranges.length; i++) {
                int a = ranges[i][0];
                int b = collatz.size() + ranges[i][1] - 1;
                if (a > b) {
                    answer[i] = -1;
                }else{
                    answer[i] = computeSize(a, b);
                }
            }
            return answer;
        }

        private double computeSize(int a, int b) {
            double sum = 0;
            for (int i = a; i < b; i++) {
                sum += size[i];
            }
            return sum;
        }

        private void getSize() {
            for (int i = 0; i < collatz.size() - 1; i++) {
                size[i] = (double) (collatz.get(i) + collatz.get(i + 1)) / 2;
            }
        }

        private void getCollatz(int k) {
            while (k != 1) {
                collatz.add(k);
                if (k % 2 == 0) {
                    k /= 2;
                }else{
                    k = k * 3 + 1;
                }
            }
            collatz.add(k);
        }
    }

130번 두 원 사이의 정수 쌍

/*
문제 분석
1. 정보
    - x축과 y축으로 이루어진 좌표계에 중심이 원점인 서로 다른 크기의 원이 두개가 주어짐

2. 목표
    - 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때 두 원 공간 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return

3. 제약 조건
    - 1 <= r1 < r2 <= 1000000

풀이
1. 아이디어
    - 반지름이 r1, r2이므로 Math.abs(x^2 + y^2)가 r1 과 r2 사이에 존재하면 두 원 사이 공간에 존재함.
    - x와 y의 좌표가 양수인 공간에서 모든 점의 좌표를 구한 후, 결과값 * 4 해줌
    - (r2 - r1 + 1) * 4 한 값을 추가한 후 return
*/

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

            for (int i = 1; i <= r2; i++) {
                double y1 = dist(r1, i);
                double y2 = dist(r2, i);
                answer += ((long) y2 - (long) Math.ceil(y1) + 1);
            }
            answer *= 4;
            return answer;
        }

        public double dist(int x, int y) {
            return (double) Math.sqrt(Math.pow(x, 2) - Math.pow(y, 2));
        }
    }