리트코드 - 1493. Longest Subarray of 1's After Deleting One Element

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

LeetCode - The World's Leading Online Programming Learning Platform

슬라이싱 윈도우 기법을 활용해 볼 수 있는 문제를 하나 더 풀어보았다.

목표는 배열에서 정확히 하나의 요소를 제거한 후 가장 긴 1의 하위 배열을 찾는 것이다.

 

def longestSubarray(nums):
    left = 0
    zero_count = 0
    max_length = 0

    for right in range(len(nums)): # O(n)
        if nums[right] == 0: # O(1)
            zero_count += 1

        while zero_count > 1: # O(m)
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        max_length = max(max_length, right - left)

    return max_length

 

왼쪽과 오른쪽의 두 포인터를 사용해 현재 창의 경계를 정의했다. zero_count는 현재 창의 0 개수를 추적하는 변수다. max_length는 찾은 하위 배열의 최대 길이를 저장하는 변수다.

오른쪽 포인터로 배열을 반복하면서. 0을 발견하면 zero_count를 증가시키도록 했다. 요소를 하나만 제거할 수 있는게 조건이기 때문에zero_count가 1을 초과하면 왼쪽 포인터를 오른쪽으로 이동하여 창을 왼쪽에서 축소한다. 0을 전달하면 zero_count가 감소한다.

지금까지 찾은 최대 길이(오른쪽 - 왼쪽)로 max_length를 업데이트한다. 요소 하나를 삭제해야 하므로 이때 1을 더하지 않는다.
루프가 끝나면 최대 길이는 요소 하나를 삭제한 후 가장 긴 하위 배열의 길이가 된다.

 

시간 복잡도: O(n). 전체 배열을 한 번만 순회하므로 시간 복잡도는 입력 배열의 크기에 따라 달라진다.
공간 복잡도: O(1). 고정된 수의 변수만 생성하므로 공간 복잡도는 일정하다.