Today I Learned

오늘 할일
1. LeetCode
2. 강의듣기
3. 싱가포르 여행계획 수정
4. 노트북 파일권한문제 해결
5. 창의 엔트리 아이디어 구상

오늘 한일
1. LeetCode

• 643. Maximum Average Subarray 1는 정수 배열에서 k길이의 서브배열의 평균값 중 가장 큰 값을 리턴하는 문제이다. 이중for문을 사용하여 해결하였다

import java.util.Arrays;

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int size=nums.length;
        double[] averages=new double[size-k+1];
        int sum=0;
        for(int i=0; i<size-k+1; i++){
            sum=0;
            for(int j=i; j<i+k; j++){
                sum+=nums[j];
            }
            averages[i]=sum*1.0/k;
        }
        return Arrays.stream(averages).max().getAsDouble();
    }
}

그리고 지금까지 착각했던게 ㅋㅋㅋ Beats5.02%가 상위퍼센트가 아니라 하위퍼센드였네.. 오른쪽 공강복잡도에 75.99%로 박수표시되어있는 것을 보니 확실하게 알 수 있다.

어차피 내일 풀 middium문제도 슬라이딩 윈도우니 내친김에 최적화를 진행해보자.

averages의 타입을 double 배열에서 ArrayList로 변경 2625ms(-9ms)
averages의 타입을 double 배열에서 LinkedList로 변경 2634ms(+9ms)
윈도우 평균값 계산을 sublist로 만들어 average계산 Time Limit Exceeded
슬라이딩 시 새로 추가되고 새로 삭제되는 값만 반영하여 평균값 계산 16ms(-2609ms)

import java.util.*;

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int size=nums.length;

        List averages=new ArrayList();

        //초기값 세팅
        double avg=0;
        for(int i=0; i<k; i++)
            avg+=nums[i];
        avg/=k;
        averages.add(avg);

        for(int i=k; i<size; i++){//i는 새로 반영할 인덱스
            avg=avg+(nums[i]-nums[i-k])*1.0/k;
            averages.add(avg);
        }
        return (double) Collections.max(averages);
    }
}

꽤나 많은 발전이 있었다. 추가적으로 진행하고싶지만 새로운 알고리즘은 통계적으로 해결하는 것 외에는 생각나는 게 없어서 마무리 하겠다.

• 싱가포르 여행일정 수정_ https://velog.io/@gogogi313/Today-I-Learned-vznmvcwf

가바베 밤에 보고시픔
13일 관광코스 +1. 칠리크랩. 저녁 6시
15일 센토사 오전에ㄱㄱ 안에서 해결. 샤워
16일 +-수영장
버스투어?