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

1. 문제 이해

이진 리스트 nums가 주어진다.

리스트에서 하나의 요소를 무조건 삭제한다.(1로만 이루어진 리스트도!)

이후 1로 이루어진 가장 긴 부분 리스트의 길이를 리턴한다.

그런 부분 리스트가 없다면 0을 리턴한다.

 

 

2. 풀이 과정

슬라이딩 윈도우 기법을 활용한다.

start 포인터를 0으로 초기화한다.

end 포인터를 for문을 통해 이동시킨다.

 

만약 nums[end]가 0이라면 zero_cnt를 1만큼 증가시킨다.

zero_cnt가 1보다 큰 경우 start 포인터를 증가시키며 zero_cnt를 1 이하로 조정한다.

 

즉 start, end 포인터는 윈도우에 0이 1개 이하로 포함되도록 한다.

 

1로만 이루어진 리스트에서도 반드시 하나의 요소를 삭제해야 한다.

따라서 end - start가 리스트에서 하나의 요소를 삭제했을 때, 1로 이루어진 가장 긴 부분 리스트의 길이를 의미한다.

 

 

3. 전체 코드

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        start = 0
        cnt = 0
        max_cnt = 0
        zero_cnt = 0

        for end in range(len(nums)):
            if nums[end] == 0:
                zero_cnt += 1
            
            while zero_cnt > 1:
                if nums[start] == 0:
                    zero_cnt -= 1
                start += 1
            
            max_cnt = max(max_cnt, end - start)

        return max_cnt

 

 

4. 생각할 점

- 반드시 하나의 요소를 삭제해야 한다는 문제의 조건을 잘 읽자.

- zero_cnt와 같이 필요한 변수를 직관적으로 설정하는 발상

 

 

5. 출처

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