[LeetCode] 1004. Max Consecutive Ones III

문제 출처: https://leetcode.com/problems/max-consecutive-ones-iii/

Max Consecutive Ones III - LeetCode

 

문제

이진 배열 nums와 정수 k가 주어진다. k개의 0을 뒤집을 수 있을 때, 배열에서 연속된 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.

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.

 

풀이

투포인터 알고리즘을 이용해서 투포인터 사이 0의 개수가 k개 이하로 유지되게끔 유지하는 방법으로 O(n) 시간 내에 답을 도출할 수 있을 것이라 생각하고 접근하였다.

 

투포인터를 이용하여 배열을 탐색하며 벌어질 일을 그림으로 그려보면, nums = [1,1,1,0,0,0,1,1,1,1,0] 이고 k = 2 일때 다음과 같다.

위 그림에서 몇가지 규칙을 찾아보면,

 

첫째, 각 단계마다 오른쪽 끝 부분의 위치가 1씩 증가한다.
둘째, 주황색 내부 0의 개수가 k보다 커지게 되면, 주황색 내부에서 제일 왼쪽있는 0을 제거함과 동시에 그 위치를 조정한다.

 

이와 같은 규칙을 다음과 같이 코드를 작성할 수 있다.

var longestOnes = function(nums, k) {
    let ans = -Infinity;

    let zeroNums = 0;

    // 투 포인터 알고리즘에 이용할 left, right 변수
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        // 현재 nums[right] 값에 따라 left를 조정
        if (nums[right] == 0) {
            if (zeroNums < k) {
                zeroNums += 1;
            } else {
                if (nums[left] == 1) {
                    // left 위치를 제일 0 중에서 제일 왼쪽에 있는 위치로 이동
                    left += 1;
                    while (left < right && nums[left]) { left += 1; }
                }
                left += 1;
            }
        }

        // right와 left의 위치 조정 이후, ans 업데이트
        ans = Math.max(ans, right - left + 1);
    }

    return ans;
}

 

Github: 1004.js

opwe37/Algorithm-Study