리트코드 1004. Max Consecutive Ones III

 

https://leetcode.com/problems/max-consecutive-ones-iii/description/?envType=study-plan-v2&envId=leetcode-75

LeetCode - The World's Leading Online Programming Learning Platform

하위 배열 문제를 처리하기 위한 일반적인 접근 방식인 슬라이딩 윈도우기법을 기반으로 해결했다.

def longestOnes(nums, k):
    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 # O(1)

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

        max_length = max(max_length, right - left + 1)

    return max_length

 

현재 창의 시작과 끝을 나타내는 왼쪽과 오른쪽의 두 개의 포인터로 시작한다.

변수 zero_count는 현재 창에 있는 0의 개수를 추적하고, max_length는 지금까지 찾은 0 중 가장 긴 하위 배열의 길이를 저장한다.
이후 오른쪽 포인터로 배열을 반복한다. 0을 발견하면 zero_count를 증가시킨다.

 

zero_count가 k를 초과하면 더 이상 0을 1로 바꿀 수 없다는 뜻이다. 따라서 zero_count가 k보다 작거나 같을 때까지 왼쪽 포인터를 오른쪽으로 이동하고, 0을 지나면 zero_count를 감소시킨다. -> O(m)

창을 조정한 후 현재 창의 길이를 계산하고 현재 창이 더 길면 max_length를 업데이트한다. 배열을 반복한 후 최대 길이에는 최대 k개의 0이 1로 반전된 가장 긴 하위 배열의 길이가 포함된다.

 

시간복잡도는 배열의 길이만큼 순회하므로 O(n)이다.

공간복잡도는 추가적인 자료구조를 생성하지 않고 상수 값만을 생성하므로 O(1)이다.