[LeetCode] Longest Subarray of 1's After Deleting One Element

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/?envType=study-plan-v2&envId=leetcode-75

 

Given a binary array nums, you should delete one element from it.
Return the size of the longest non-mpty subarray containing only 1's in the resulting array.

Return 0 if there is no such subarray.

Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:
1 <= nums.length <= 105
nums[i] is either 0 or 1.

---

nums가 주어지고.. 거기서 0이든 아니든!!! 하나의 엘리먼트를 지워야 함.

1만 갖고 있는 비어 있지 않은 부분 배열의 길이를 리턴해라.

그런 게 없으면 0을 리턴해라.

 

const convertNums = (nums) => {
    const res = [];
    let current = 0;
    for(let i=0; i < nums.length; i++){
        if(nums[i] == 0){
            if(isNaN(res[current])){
                res[current] = -1;
            }else if(res[current] > 0){
                current++;
                res[current] = -1;
            }else{
                res[current]--;
            }
        }else{
            if(isNaN(res[current])){
                res[current] = 1   
            }else if(res[current] < 0){
                current++;
                res[current] = 1; 
            }else {
                res[current]++;  
            }
        }
    }
    return res;
}
const longestSubarray = function(nums) {
    // nums가 주어지고.. 거기서 하나의 엘리먼트를 지워야 함.
    // 1만 갖고 있는 비어 있지 않은 부분 배열의 길이를 리턴해라.
    // 그런 게 없으면 0을 리턴해라.
    let start = 0;
    let end = 0;
    const compact = convertNums(nums);
    if(compact.length == 1){
        return compact[0] > 0 ? compact[0] - 1 : 0;
    }
    let result = 0;
    let sum = 0;
    for(let i=0; i < compact.length; i++){
        let prev = isNaN(compact[i-1]) ? 0 : compact[i-1];
        let next = isNaN(compact[i+1]) ? 0 : compact[i+1];
        if(compact[i] == -1){
            sum = prev + next;
        }
        if(compact[i] < -1){
            sum = prev > next ? prev : next;
        }
        result = result > sum ? result : sum;
    }

    return result;
};

 

이렇게 푸니까 통과는 됐음. 근데 또 슬라이딩 윈도우는 아니다. ^_^ 

그냥 어제 생각했던 방식이 이번에는 통할 것 같아서 써봤을 뿐...

연속된 1과 0의 수를 압축해서 배열로 뽑고... 0이 1개면 바꿔보고 앞뒤 더해서 저장.

더 작으면... 앞과 뒤 중 더 큰걸 채택해서 저장.

결과적으로 그렇게 뽑은 수 중 제일 큰 걸 리턴하도록 한다.

 

사실상 어제 푼 거랑 완전 같은 문제다. 지울 수 있는 0의 수만 제한됐고...

var longestSubarray = function (nums) {
    let left = 0;
    let right = 0;
    let k = 1;
    while(right < nums.length){
        if(nums[right] == 0){
            k--;
        }
        if(k<0){
            if(nums[left] == 0){
                k++;
            }
            left++;
        }
        right++;
    }

    return right - left - 1;
};

 

이런 생각 어떻게 그냥 사람 머리로 하는걸까? 사실 컴퓨터 아닐까?

 

 

그와중에 discussion에서 발견한 웃긴 댓글ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ