코딩 테스트 [프로그래머스] - 우박수열 정적분

문제 링크

합배열을 이용해 풀었다.

---

전체 코드

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        
        double[] answer = new double[ranges.length];
        
        HashMap<Integer, Double> map = new HashMap<>();
        map.put(0, 0.0);
        
        int n = 0;
        
        while(k > 1){
            int kNext = 0;
            
            if(k % 2 == 0)
                kNext = k / 2;
            else
                kNext = (k * 3) + 1;
            
            n++;
                
            int heightS = Math.max(k, kNext);
            int heightT = Math.abs(k - kNext);
            double area = (double)heightS - ((double)heightT / 2);
            
            map.put(n, area + map.get(n - 1));
            
            k = kNext;
        }
        
        for(int i = 0; i < ranges.length; i++){
            int a = ranges[i][0];
            int b = n + ranges[i][1];
            
            double ans = 0.0;
            
            if(a > n || b > n){
                answer[i] = -1.0;
                continue;
            }
            
            if(a > b)
                answer[i] = -1.0;
            else if(a == b)
                answer[i] = 0.0;
            else{
                answer[i] = map.get(b) - map.get(a);
            }
        }
        
        return answer;
    }
}

---

정답 배열의 크기를 주어진 ranges 배열의 크기로 선언했다.
그후 정적분의 합 배열이 될 <Integer, Double> 쌍을 가지는 HashMap을 만들었다.
그 후 <0, 0.0> 을 HashMap에 넣었다.

        double[] answer = new double[ranges.length];
        
        HashMap<Integer, Double> map = new HashMap<>();
        map.put(0, 0.0);

문제로 주어진 콜라크 추측을 한 횟수를 저장할 n을 선언하고 0으로 초기화했다.
그 후 콜라크 추측으로 주어진 k값이 1이 될 때까지 반복문을 돌린다.

• 콜라크 추측

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

        int n = 0;
        
        while(k > 1){
            ...
        }

반복문을 반복하며 n을 증가시키고 k값을 갱신시킨다.
또한 k가 갱신될때마다 합 배열을 저장하는 HashMap에 값을 입력한다.
입력하는 값은 n을 key으로 하며 0 ~ n 사이의 우박수열의 정적분 값을 value로 하는 데이터쌍이다.

        int n = 0;
        
        while(k > 1){
            int kNext = 0;
            
            if(k % 2 == 0)
                kNext = k / 2;
            else
                kNext = (k * 3) + 1;
            
            n++;
                
            int heightS = Math.max(k, kNext);
            int heightT = Math.abs(k - kNext);
            double area = (double)heightS - ((double)heightT / 2);
            
            map.put(n, area + map.get(n - 1));
            
            k = kNext;
        }

합 배열을 완성시켰으면 다음은 ranges로 주어지는 구간의 우박수열의 정적분 값을 구해 answer 배열에 넣어준다.

시작값 a 와 끝나는 값 b를 구하고

a나 b가 최대 범위인 n을 벗어나면 -1.0을,
시작값인 a가 끝나는 값인 b보다 크면 -1.0을,
a와 b가 같다면 0.0을 넣어준다.

그 외엔 우박수열의 정적분 값을 구해준다.
a ~ b의 정적분 값은 (0 ~ b)의 정적분 값에서 (0 ~ a)의 정적분 값을 빼준 값과 같다.
합 배열을 저장한 HashMap에는 n을 key 값으로 0 ~ n 의 정적분 값을 저장해두었으므로 이를 이용해서 정적분 값을 구해 넣어준다.

        for(int i = 0; i < ranges.length; i++){
            int a = ranges[i][0];
            int b = n + ranges[i][1];
            
            double ans = 0.0;
            
            if(a > n || b > n){
                answer[i] = -1.0;
                continue;
            }
            
            if(a > b)
                answer[i] = -1.0;
            else if(a == b)
                answer[i] = 0.0;
            else{
                answer[i] = map.get(b) - map.get(a);
            }
        }
        
        return answer;
    }