[구현] 우박수열 ( 실패분석 - 아이디어)

byeol·2023년 5월 25일
0
post-thumbnail

접근

우박수열

두가지 부분에서 좀 버벅거렸습니다.

하나는 갑자기 등장한 정적분과
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;
    }
}
profile
꾸준하게 Ready, Set, Go!

0개의 댓글