[ 99클럽/챌린저 ] 10일차 TIL : 우박수열

NaHyun_kkiimm·2024년 4월 10일

99일지 99클럽 Java TIL 개발자스터디 알고리즘 코딩테스트 프로그래머스 항해

99클럽

목록 보기

11/13

문제 요약

이번 문제는 설명이 길어 생략합니다. >-<

[ 예시 ]

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]

[ 제약 조건 ]

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

[ 프로그래머스 ]

Java
출처) https://school.programmers.co.kr/learn/courses/30/lessons/134239

풀이

누적합을 이용하였다.
(1) 1이 완성되는데 드는 횟수를 나타낼 n과 넓이를 누적할 prefix를 선언한다.
(2) (0, k)일 때는 넓이가 0임으로, 미리 저장(add)한다.
(3) k>1일 때까지 반복하며, 문제에 주어진 조건을 수행한다.
이 때, 넓이를 구하기 위해선 이전 수행으로 완성된 k(y)와 현재 k값이 필요하기에 prev 변수에 미리 저장하고, 이를 이용하여 넓이를 구한다.
또한, 현재 넓이 결과값과 이전 넓이 결과값을 더하여 prefix에는 누적으로 넓이 합이 저장되도록 한다.
prev값을 현재 k값으로 저장하여 이후 계산에 사용하도록 한다.
k를 1로 만들 때까지 든 횟수를 세기 위해 n++을 수행한다.

(4) ranges에서 말하는 범위를 구한다.

만일 x와 y가 같다면 0.0을 저장한다.
만일 x>y일 경우, 아래 문제에 맞게 -1.0을 저장한다.

단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

(5) 구해진 결과값을 answer에 넣는다.
예를 들어, 범위가 [1, 3]일 경우 [0, 3] - [0, 1] 형식 누적합을 통해 쉽게 구할 수 있다.

Code

import java.util.*;
class Solution {
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];
        double prev = k;
        int n = 1;
        ArrayList<Double> prefix = new ArrayList<>();
        prefix.add(0.0);
        while (k>1) {
            if (k%2==0) k/=2;
            else k = 3*k + 1;
            double num = prefix.get(n-1) + (k+prev)/2;
            prefix.add(num);
            prev = k;
            n++;
        }
        
        for(int i=0;i<ranges.length;i++) {
            int x = ranges[i][0];
            int y = n-1 + ranges[i][1];
            
            if (x==y) {
                answer[i] = 0.0;
                continue;
            }
            else if (x>y) {
                answer[i] = -1.0;
                continue;
            }
            answer[i] = prefix.get(y)-prefix.get(x);
        }
        
        
        return answer;
    }
}

시도

정적분부터 다시 공부하기
: 수학을 놓은지 언 5년..부끄럽게도 정적분이라는 말을 듣자마자 숨이 턱 막혔다. 배웠던 수학의 모든 내용이 사라졌기 때문이다. 급하게 친구에게 전화해 정적분의 설명을 듣고, 문제를 풀려했으나 젠장..직선 그래프이기 때문에 굳이 알 필요가 없었다. ㅎㅎ
k *= 3 + 1;으론 원하는 값을 얻을 수 없다.
해당 코드가 k = k*3 + 1인 줄 알고 저렇게 짠 건데 왠 걸 내가 원하는 k값이 나오지 않았다. 3을 먼저 곱하고, +1을 진행하는 줄 알았지만, 실상은 3 + 1을 먼저 진행하고 *3을 진행해서 그만 메모리 부족이 떴다. 간단한 건 좋으나 조심하자..