[프로그래머스/JAVA] 코딩테스트 연습 > 연습문제 > 우박수열 정적분(by 다알쥐AI)

[우박수열 정적분] 코딩테스트 연습 > 연습문제 > 우박수열 정적분

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

콜라츠 추측이란 로타르 콜라츠(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이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. 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이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

---

입출력 예

---

입출력 예 설명

입출력 예 #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일 지문 오탈자가 수정되었습니다.

---

[간단설명]

우박수열을 계산해서, 주어진 구간의 정적분 구하기(넓이 구하기)

 

[접근방법]

1. 우박수열을 계산한다.

2. 우박수열(x)의 각 구간(y) 별로 넓이를 저장한다.

3. 주어진 구간(ranges)의 x(a~n-b) 범위 만큼 넓이를 더한다.

4. 시작점이 끝점보다 커서 계산할수 없는 경우(즉, a>n-b) -1.0 처리해준다.

5. 정답 배열을 리턴한다.

 

[주의사항]

1. 우박수열의 각 구간별 넓이를 구할때, 사다리꼴 넓이를 구해야 하는데, 윗변을 계산할 수 없으므로, 위에 삼각형 + 아래 사각형을 구하는 방식으로 접근하자.

2. 주어진 구간의 범위를 계산할 때, b는 -로 주어지기 때문에 n+b를 하면 끝점을 구할 수가 있다(문제가 이상하다)

3. 시작점이 끝점보다 큰 경우는 -1.0을 해줘야 한다.

 

[소스공개]

import java.util.*;
class Solution {
    public double[] solution(int k, int[][] ranges) {
        // 정답 리스트
        List<Double> answer = new ArrayList<>();
        // 넓이 리스트
        List<Double> list = new ArrayList<>();
        // 우박수열 구하고, 각 구역의 넓이를 리스트로 받아온다.
        list = collatz(k,list);
        // 우박수열 개수 n
        int n = list.size();
        
        // ranges는 x의 범위만큼 정적분 한다(넓이를 더한다)
        // r[0] => a, r[1] => b
        // ex) [1,-2] 구간 : 1(a=1) ≤ x ≤ 3(n=5,b=-2)
        for(int[] r : ranges){
            double sum = 0L;
            // 구간의 시작점이 끝점보다 커서 유효하지 않은 구간
            if(r[0]>n+r[1]){ 
                sum=-1.0;
            }else{
                for(int i=r[0];i<(n+r[1]);i++){
                    sum+=list.get(i);
                }
            }
            answer.add(sum);
                
        };
        // 정답 배열 리턴
        return answer.stream().mapToDouble(Double::doubleValue).toArray();
    }
    
    // 우박수열(콜라츠 추측) 
    public List<Double> collatz(int k1, List<Double> list){
        int k2=0;
        // 1-1. 입력된 수가 짝수라면 2로 나눕니다.
        if(k1%2==0){
            k2=k1/2;
        // 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
        }else{
            k2=k1*3+1;
        }
        // 넓이 구하기(위에 삼각형 + 아래 사각형)
        double dimensions = Math.abs(k1-k2)*1/(double)2 + Math.min(k1,k2)*1;
        list.add(dimensions); // 리스트에 현재 구간의 넓이 저장
        // 2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.
        if(k2>1){
            return collatz(k2,list);
        }else{
            return list;
        }
    }
}

 

[실행결과]