우박수열 정적분(Java)

bearMin·2024년 3월 25일

🎯문제

콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.

은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 초항이 k인 우박수열이 있다면, x = 0일때 y = k이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.
그림.png

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다. 0 이상의 수 b에 대해 [a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미합니다.

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

제한사항

2 ≤ k ≤ 10,000
1 ≤ ranges의 길이 ≤ 10,000
- ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

입출력 예

k	ranges	result
5	[[0,0],[0,-1],[2,-3],[3,-3]]	[33.0,31.5,0.0,-1.0]
3	[[0,0], [1,-2], [3,-3]]	[47.0,36.0,12.0]

입출력 예 설명

입출력 예 #1

5로 시작하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 그래프에서 꺾이는 지점을 경계로 5개의 구역 넓이를 구하면 각각 10.5, 12, 6, 3, 1.5 입니다.

입출력 예 #2

3으로 시작하는 우박수열은 3 ⇒ 10 ⇒ 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 그래프에서 꺾이는 지점을 경계로 3개의 구역 넓이를 구하면 각각 47, 36, 12 입니다.

※ 공지 - 2023년 08월 11일 문제 지문이 리뉴얼되었습니다. 기존에 제출한 코드가 통과하지 못할 수도 있습니다.
※ 공지 - 2023년 09월 06일 지문 오탈자가 수정되었습니다.

✏️풀이

코드

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];
        // 우박수열 저장
        List<Integer> list = new ArrayList<>();
        
        // 우박수열 구하기
        while(k > 1) {
            list.add(k);
            
            // 짝수라면 2로 나눠줌
            if(k % 2 == 0) {
                k /= 2;
            }
            // 홀수라면 3을 곱한 뒤 1을 더해줌
            else {
                k = k * 3 + 1;
            }
        }
        
        // 마지막 수 저장
        list.add(k);
        
        // 범위의 개수만큼 반복
        for(int i = 0; i < ranges.length; i++) {
        	// 올바르지 않은 범위라면 -1을 저장
            if(ranges[i][0] > ranges[i][1] + list.size() - 1) {
                answer[i] = -1;
                continue;
            }
            // 같은 자리라면 0을 저장
            else if(ranges[i][0] == ranges[i][1] + list.size() - 1) {
                answer[i] = 0;
                continue;
            }
            
            // 넓이를 저장할 변수
            double area = 0;
            // 구해야하는 범위만큼 반복
            for(int j = ranges[i][0]; j < ranges[i][1] + list.size() - 1; j++) {
            	// 넓이를 구해서 저장
                area += (list.get(j) + list.get(j+1)) / 2.0;
            }
            
            // 구한 넓이를 answer에 저장
            answer[i] = area;
        }
        
        return answer;
    }
}

설명

반복문을 사용해서 진행하였다.

우박수열을 저장할 List를 생성한다.

while문을 사용해서 우박수열을 구해주는데 우박수열은 k의 값이 1이 될때까지 진행을 하는 것으로, 짝수라면 2로 나눠주고 홀수라면 3을 곱한 뒤 1을 더해주는 방식을 반복하는 것이다.

해당 while문을 빠져나오면 k의 값은 1이 되고, 마지막 1까지 List에 저장한다.

구해야하는 값의 개수만큼 반복을 진행한다. 범위는 [0, -2] 의 형식으로 주어지며 앞은 시작위치, 뒤는 list.size()로부터 떨어진 거리를 뜻한다.
이때, 총 길이는 5이고 [3, -4]일 때 시작위치는 3이고, 종료위치는 0이 된다. 이는 올바르지 않은 범위이기 때문에 -1을 반환해주어야한다.

만약 총 길이는 5이고, [3, -1]일 경우에는 시작위치는 3이고, 종료위치 역시 3이 된다. 이때는 0을 반환해주어야한다.

만약 총 길이는 5이고, [2, -1]일 경우에는 시작위치는 2이고, 종료위치는 3이 된다. 이때, 2와 3 범위를 구해서 반환해주어야한다.

ranges 배열의 값을 확인해서 범위를 확인한다. 올바른 범위라면 사다리꼴의 넓이를 구해준다. 사다리꼴의 넓이를 구하는 공식은 (윗변 + 아랫변) * 높이 / 2 이다.

위의 모든 반복이 끝난 뒤 answer 배열을 반환해주면 문제를 해결할 수 있다!