Today I Learned

오늘 할일
1. LeetCode
2. 창엔 조교 과제(담당학생 초대 및 교재 검토) 수행 및 발표 준비
3. 등록금, 사회봉사 확인

오늘 한일
1. 창의엔트리 담당학생 공지방 초대, 교육자료 검토 이상 없음, 발표는 틴거캐드에 그림을 그려서 실제 시연을 보여줄 예정. 혹은 영상촬영
2. 등록금 이번주 금요일까지 등록, 사회봉사 승인완료
3. LeetCode

• 1004. Max Consecutive Ones III을 마저 생각해보자..
        기존에 고안한 알고리즘인 0의 배열정보로 sliding window를 수행하기에는 그 사이의 1을 따로 계산해야하기에 비효율적이다. 가장 간단한 방식으로 순차적으로 for하며 0이 나올경우 범위를 ++하는 방법이 가장 간단할 것 같다? 비효율적이더라도.

다음은 중첩반복문으로 가장 간단하게 작성해본 코드이다.

    public int longestOnes(int[] nums, int k) {
        int max=0;
        int size=nums.length;
        int max_1=0;

        for(int i=0; i<size; i++){
            int life=k;
            int count_1=0;
            //i를 시작으로 윈도우를 탐색한다. k개의 0을 1로 간주하고 연속된 1의 개수를 센다
            int j;
            for(j=0; i+j<size; j++){
                //1인상황은 j를 그냥 증가
                if(nums[i+j]==0){//0을 만났는데
                    if(life!=0){//flip가능하다면
                        life--;
                    } else{
                        break;
                    }
                }
            }
            count_1=j;
            if(count_1>max_1)
                max_1=count_1;
        }

        return max_1;
    }

바로 통과를 했다...?? 최적화를 더 시키라고 런타임 제한이 더 있을 줄 알았는데 해결에 주안점을 준 문제같다. 나도 처음 접근할 때 반복문만으로 해결하기 보다 최적화를 시켜보고 싶었는데 알맞게 k개의 0을 1로 바꾸어 최대길이의 1을 만들으라는 문제에서 손쉬운 최적화 기법을 생각해내지 못했다. 코드가 너무 길어지는 것 보단 가장 간단한 코드가 좋을지도..?

• 1493. Longest Subarray of 1's After Deleting One Element는 이진배열에서 하나의 원소를 삭제해서 1로만 이루어진 서브배열의 최대길이를 리턴하는 것이다.

다음은 위의 문제와 같이 life변수를 사용해서 작성한 코드이다.

 public int longestSubarray(int[] nums) {
        /*
        이진 배열에서 하나의 원소를 지워야한다.
        1로만 이루어진 비어있지 않은 최대 길이의 서브배열 길이를 리턴해라. 만약 없다면 0을 리턴
         */
        int size=nums.length;
        int max_len=0;
        //0을 무시하거나, 1로만 이루어져있어 1을 무시하거나
        List list=Arrays.stream(nums).boxed().collect(Collectors.toList());
        if(list.contains(0) && list.contains(1)){
            for(int i=0; i<size; i++){//슬라이딩 시작 인덱스
                if(nums[i]==0)
                    continue;
                int length=0;
                int life=1;
                int j;
                for(j=i; j<size; j++){
                    if(nums[j]==0){
                        if(life!=0){
                            life--;
                        } else{
                            break;
                        }
                    }
                }
                length=j-i+1;

                if(life==0)
                    length-=2;
                if(max_len<length)
                    max_len=length;
            }
        } else if(list.contains(0)){
            return 0;
        } else if(list.contains(1)){
            return size-1;
        } else{
            return 0;
        }
        return max_len;
    }

오답의 이유는 length를 계산할 때 시작 index인 i와 중첩 반복index인 j를 사용하여 j-i+1로 계산을 했는데, 배열의 끝까지 도달한 경우 j가 ++되어 끝 인덱스보다 한칸 뒤의 인덱스를 가리키기 때문이다. 이 경우를 막기 위해 내부의 for루프가 끝난 경우 j--를 수행하여 정확한 연속1배열의 끝 원소 인덱스를 가리키게 수정하였다.

• 1732. Find The Highest Altitude는 자전거 코스의 node간의 상대적인 고도차이가 저장된 배열을 이용하여 절대적인 고도가 가장 높은 node의 절대고도를 구하는 문제이다. 가장 간단하게 코드를 작성해보았다.

class Solution {
    public int largestAltitude(int[] gain) {
        int max=0;
        int current_gain_sum=0;
        for(int i=0; i<gain.length; i++){
            current_gain_sum+=gain[i];
            if(max<current_gain_sum)
                max=current_gain_sum;
        }
        return max;
    }
}

만점을 기록하였다! 간단한거 최고