[LeetCode] 1004. Max Consecutive Ones III

🔗 Problem Link

https://leetcode.com/problems/max-consecutive-ones-iii/description/

---

❔Thinking

• 0과 1로 이루어진 숫자 배열이 주어질 때, k개의 0을 1로 바꾸어 만들 수 있는 1 부분 수열의 최대 길이를 반환한다.
  • ex - 0 0 1 1 1 0 1, k=1 이라면 111 0 1에서 0을 1로 바꾸어 11111을 만들 수 있으므로 5 반환

---

💻Solution

1. left, right Two-Pointer를 활용한 풀이

• left와 right로 0을 1로 바꾼 횟수가 k를 넘지 않도록 window 구성
• 만약 현재 0을 1로 바꾼 횟수가 k를 넘은 경우, left를 이동하여 cur_zero_cnt를 k보다 작게 유지한다.
• right-left+1로 window의 길이를 계산한다. 

def longestOnes(self, nums: List[int], k: int) -> int:
    left = 0
    max_length = 0
    cur_zero_cnt = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            cur_zero_cnt += 1
        while cur_zero_cnt > k:
            if nums[left] == 0:
                cur_zero_cnt -= 1
            left += 1
        max_length = max(max_length, right-left+1)

    return max_length

---

🗝️keypoint

1. nums[right]이 0인지 1인지 확인하는 단계를 우선 수행해서, 마지막이 1인 경우에도 max_length를 계산할 수 있도록 한다.