두가지 부분에서 좀 버벅거렸습니다.
하나는 갑자기 등장한 정적분과
offset을 이용한 범위입니다.
정적분은 사실 넓이의 개념이며
이 문제의 경우 무조건 사다리꼴의 넓이 공식을 기억해야 풀 수 있습니다.
사다리꼴의 넓이 = (윗변+아랫변)*높이/2
그리고 두 번째인 offset을 이용한 범위 부분입니다.
처음에 범위에 음수가 등장해서 무엇을 말하는지 감이 잡히지 않았습니다.
시간을 재고 풀다 보니 마음이 급해져 문제가 눈에 잘 들어오지 않았습니다.
문제에 주어진 예시에 따라 offset을 표시해보았습니다.
양쪽 끝 단에서 얼마나 떨어졌나는 나타내기 때문에 위와 같이 표현되었음을 알게 되었습니다.
결국은 아래와 같은 결과가 완성됩니다.
사다리꼴의 넓이 공식을 이용해서 구했습니다.
그리고 ArrayList에 각각의 넓이를 누적해서 더해주었습니다.
0번째는 0
1번째는 0+10.5+12
2번째는 0+10.5+12+6
3번째는 0+10.5+12+6+3
4번째는 0+10.5+12+6+3+1
0을 넣어준 이유는 문제에서 주어지는 ranges라는 2차원 배열에 따라 계산을 더 쉽게하기 위함입니다.
위와 같이 누적하여 저장함으로써 만약에
[0,0]이라면
<list의 N+0번째 - list의 0번째>와 같은 형태로 표현할 수 있게 됩니다.
여기서 N은 반대편에서 시작하는 offset의 위치를 파악하기 위한 것은
총 만들어지는 사다리꼴의 개수
즉 y가 1이 된 순간의 x의 좌표입니다.
따라서 풀이는 아래와 같습니다.
import java.util.*;
class Solution {
public double[] solution(int k, int[][] ranges) {
ArrayList<Double> answer = new ArrayList<>();
//사다리꼴 넓이= [(윗변 + 아랫변) × 높이 ÷ 2]
answer.add((double)k);
while(k>1){
if(k%2==0){
k=k/2;
}else{
k=k*3+1;
}
answer.add((double)k);
}
ArrayList<Double> result = new ArrayList<>();
result.add(0.0);
for(int i=0;i<answer.size()-1;i++){
result.add((answer.get(i)+answer.get(i+1))/2);
}
for(int i=1;i<result.size();i++){
result.set(i,result.get(i-1)+result.get(i));
}
int size = result.size()-1;
double[] answerArr = new double[ranges.length];
for(int i=0;i<ranges.length;i++){
int start = ranges[i][0];
int end = ranges[i][1];
if(size+end<start){
answerArr[i]= -1.0;
}else answerArr[i]= result.get(size+end)- result.get(start);
}
return answerArr;
}
}