[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element 해설 및 풀이 (Python)

LeetCode 1493. 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-empty 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, 그 중 하나의 요소를 삭제해야 합니다.

결과 배열에 ' 만 포함된 가장 긴 비어 있지 않은 하위 배열의 크기를 반환합니다 . 해당 하위 배열이 없으면 반환합니다.10

 

예시 1:

입력: nums = [1,1,0,1]
 출력: 3
 설명: 위치 2의 숫자를 삭제한 후 [1,1,1]에는 1의 값을 갖는 숫자 3개가 포함됩니다.
예 2:

입력: nums = [0,1,1,1,0,1,1,0,1]
 출력: 5
 설명: 4번째 위치의 숫자를 삭제한 후, 1의 값을 가지는 가장 긴 부분 배열 [0,1,1,1,1,0,1]은 [1,1,1,1,1]입니다.
예시 3:

입력: nums = [1,1,1]
 출력: 2
 설명: 하나의 요소를 삭제해야 합니다.
 

제약 조건:

1 <= nums.length <= 105
nums[i]0또는 둘 중 하나 입니다 1.

 

---

문제 유형

배열

동적 프로그래밍

슬라이딩 윈도우

 

풀이 방법 도출

 

이 문제를 해결하기 위해서 슬라이딩 윈도우를 사용하여 풀 수 있습니다.

1. 0은 최대 1개만 제거할 수 있습니다.
2. 윈도우 내 0의 개수가 2개 이상이 된다면 왼쪽 포인터를 이동시켜 조건을 만족시킵니다.
3. 윈도우 크기는 right - left
4. 0 하나를 삭제하는 조건이므로 현재 구간의 길이에서 1을 뺀 것처럼 동작합니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left = 0  # 왼쪽 포인터
        max_length = 0  # 결과값
        zero_count = 0  # 현재 윈도우 내 0의 개수
        
        for right in range(len(nums)):
            # 오른쪽 포인터를 이동하면서 0의 개수 세기
            if nums[right] == 0:
                zero_count += 1
            
            # 윈도우 내 0이 2개 이상일 경우 왼쪽 포인터 이동
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            
            # 최대 길이 갱신
            max_length = max(max_length, right - left)
        
        return max_length