[LeetCode] Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description/?envType=study-plan-v2&envId=leetcode-75

 

Given a binary array nums and an integer k, 

return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

 

Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
 

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

---

nums라는 1과 0이 들어간 숫자 배열이 주어지고, 숫자 k가 주어진다.

배열 내에 k개만큼 0을 1로 뒤집을 수 있고, 그렇게 했을 때 최대로 연속된 1의 수를 구하는 문제다.

Sliding Window, Two pointer 알고리즘과 관련된 문제... (몰랐음)

 

처음에는 접근을 좀 이상하게 해서ㅋㅋ

[ 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 ] 라는 배열이 주어지면 이를 [ 3, 0, 0, 0, 4, 0 ] 처럼 1을 뭉쳐버리려고 했다.

아니면, 0까지 뭉쳐서 [3, -3, 4, -1] 이렇게 만든 다음 생각해보려고 했는데,

뒤집을 수 있는 0의 수 k가 일정하지 않다보니, 만약에 k가 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 convertNums2 = (nums) => {
    const res = [];
    let current = 0;
    for(let i=0; i < nums.length; i++){
        if(nums[i] == 0){
            current++;
            res[current] = 0;
        }else{
            if(isNaN(res[current])){
                res[current] = 1   
            }else if(res[current] == 0){
                current++;
                res[current] = 1; 
            }else {
                res[current]++;  
            }
        }
    }
    return res;
}


const longestOnes = function(nums, k) {
    // nums라는 숫자 배열이 주어지고 숫자 k가 주어짐
    // nums 내에 k개만큼의 0을 1로 뒤집었을때 제일 연속적으로 1이 많은 수를 구하기
    // 1. 연속적으로 1이 나오는 묶음을 갖는 배열을 구함
    // ex) [ 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 ] -> [ 3, 0, 0, 0, 4, 0 ]
    // 2. 여기서 0인 위치에 k만큼 자리를 바꾸었을 때...를 구하면?
    // 2-1. 뭘 기준으로 생각해야 하나?
    let result = 0;
    let ans = 0;
    const converted = convertNums(nums);
    console.log(converted)
    // for(let i=0; i < nums.length; i++){
    for(let i=0; i<converted.length; i++){
        if(converted[i] < 0){ //0의 묶음일때
            const zeroCount = -converted[i];
            // 0이 양수 사이에 k개보다 많이 존재하면 굳이 거기를 이을 필요가 없음
            if (zeroCount > k){
                continue;
            }
            let window = k;
            window = k + converted[i];
            if(!(converted[i-1])){
                // 맨 앞임
                // 
                result += -converted[i] + converted[i+1];
            }
            if(!(converted[i+1])){
                // 맨 끝에 도달하면 남은 zeroCount를 더해주고 끝
                result += window;
            }
            ans = ans > result ? ans : result;
        }
    }
    //     if(i < k){
    //         result += nums[i]
    //         console.log(nums[i]);
    //         ans = result > ans ? result : ans;
    //     }else{
    //         result -= nums[i-k];
    //         result += nums[i];
    //         ans = result > ans ? result : ans;
    //     }
    // }
    console.log(ans);
    return result;
};

 

아무튼 위 방식대로는 아무리 용을 써도 감이 잡히지 않아서,

문제 하단에 주어진 힌트를 읽고 투포인터와 슬라이딩 윈도우에 대한 힌트를 얻고.. 겨우 풀어냈다.

const longestOnes = function(nums, k) {
    let ans = 0;
    let flipable = k;
    let prevFlips = [];

    let start = 0;
    let end = 0;
    for(let i=0; i<nums.length; i++){
        end = i;
        if(nums[i]){
            // 만난 숫자가 1
        }
        if(!nums[i]){
            // flip한 숫자 위치를 저장
            prevFlips.push(i);
            // 만난 숫자가 0
            if (flipable){
                // flip가능
                flipable--;
            } else{
            // 이전에 flip한 위치로 start를 옮김
                start = prevFlips.shift() + 1;
            }
        }
        ans = end - start + 1 > ans ? end - start + 1 : ans;
    }

    return ans;
};

 

통과는 됐지만 효율은 안 나오는 코드인 듯하다. 

flip을 한 위치를 배열에 저장하고, 더이상 뒤집을 수 없을 때 맨 앞의 뒤집은 위치 뒤로 start를 옮겨 준다.

엄밀하게 따지면 투포인터를 이용했다고 보기도 힘들고... 굳이 배열을 쓸 필요도 없는데ㅋㅋ

그래도 솔직히.. 나한테는 이렇게 푸는 게 이해하기 좀 더 쉬운 듯... 당연함. 내가 짠 코드임ㅎㅎ

 

그래서 또 1등 코드를 훔쳐옴.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
    // Initialize left and right pointers for the sliding window
    let left = 0, right = 0;

    // Iterate through the array with the right pointer
    while (right < nums.length) {
        // If the current element is 0, decrement k since we pretend to flip it
        if (nums[right] === 0) {
            k -= 1;
        }

        // If k becomes negative, it means we have used more than the allowed flips.
        // We need to shrink the window from the left side.
        if (k < 0) {
            // If the element at the left pointer was 0, sliding past it will "refund" one flip
            if (nums[left] === 0) {
                k += 1;
            }
            // Move the left pointer to shrink the window
            left += 1;
        }

        // Move the right pointer to expand the window
        right += 1;
    }

    // The difference between the pointers gives-
    // -the maximum window (subarray) length that met the condition.
    return right - left;
};

 

원리는 결국.. 처음부터 시작해서 오른쪽 인덱스를 올리는데 0을 만나면 k를 소모하고,

k가 0보다 작아지면 왼쪽 끝 인덱스를 하나씩 올리면서 그 자리가 0이라면 k를 또 1 올려준다.

그렇게 무한히 반복하다보면 오른쪽 인덱스가 nums.length를 만나는데 그 때 오른쪽 끝과 왼쪽 끝의 차이를 리턴하면 끝...

 

슬라이딩 윈도우도 그렇고 투 포인터 알고리즘도 제대로 공부해 두면 두고두고 쓸모가 많을 듯한데,

이참에 머리에 좀 새겨야지^_^...