Today I Learned

오늘 할일
1. LeetCode
2. 강의

오늘 한일
1. LeetCode

• 1004. Max Consecutive Ones III는 0을 k번 뒤집을 수 있을 때 연속된 최대의 1 개수를 찾는 문제이다.
        처음 문제를 연속된 1의 개수를 찾는거로 이해해서 작성한 코드는 아래와 같고 인자로 주어진 k를 사용하지 않았기에 문제를 잘못이해했음을 깨달았다.

    public int longestOnes(int[] nums, int k) {
        //1이 등장하면 연이은 곳들의 수를 세기 시작하며, branch count처럼..
        int max=0;
        int size=nums.length;
        for(int i=0; i<size; i++){
            if(nums[i]==1) {//최초 1의 발견
                int count=1;
                for (int j = 1; i+j < size && nums[i+j]==1; j++) {
                    count++;
                }
                if(max<count) {
                    max = count;
                }
                i+=count-1;
            }
        }
        return max;
    }

꽤나 어렵다. 변수가 너무 많이 발생하는데, 뒤집을 k의 개수만 1로 바꿔서 1의 개수를 늘리는 게 아니라 연속된 1의 배열을 가장 효율적으로 연결시켜 가장 긴 1의 배열을 만들어야 하기 때문이다. 전략을 한번 생각해보자. 여기서 사용되는 효율적인 연결은 무엇을 뜻하는 것일까?

1의 배열들을 각각의 개체로 보았을 때 0은 개체를 키우면서도 연결시킬 수 있다. 1보다는 0에 집중해보자. 1은 우리가 건들 것이 아니다.
여기서, k보다 큰 0의 연속배열은 무의미하다. 개체를 연결시킬 수 없고 개체 크기만 키우기 때문이다. 0의 배열을 for를 통해 탐색하고 양 옆에 1유무를 판단하여 k를 소진시켜 가장 긴 1의 배열을 구할 수 있다. 만약 k보다 큰 0의 연속배열 밖에 없다면 가장 큰 1의 배열에 k값을 더할 수 있는지 확인해서 계산한다. 고려해야할 사항은 인덱스 초과. 범위체크로 해결할 수 있을 듯 하지만, 만약 가장 긴 1의 연속배열이 양 끝에 있어 인덱스가 초과되어 k를 온전히 활용할 수 없고, 중앙의 배열이 오히려 k를 전부 소진하여 최대길이를 역전하는 경우도 고려해야할 듯 하다. 우선 차차 구현해보자.

우선 위의 조건이 까다롭기에 0의 연속배열을 컨테이너에 저장해보겠다. 부가효과로 1의 연속배열 정보 역시 0의 연속배열의 start_index+length+1에서부터 다음 0연속배열 start_index-1까지임을 알아낼 수 있다.