Python – 최대 k개의 0을 뒤집어 만들 수 있는 가장 긴 연속된 1의 길이 구하기

문제 개요

0과 1로만 이루어진 이진 리스트가 하나 주어지고, 숫자 k가 함께 제공됩니다. 우리는 최대 k개의 0을 1로 바꿀 수 있으며, 그 결과 모든 요소가 1인 가장 긴 연속 부분 리스트(sublist)의 길이를 구해야 합니다.

예를 들어 입력이 nums = [0, 1, 1, 0, 0, 1, 1], k = 2라고 해 보겠습니다. 가운데에 있는 두 개의 0을 1로 바꾸면 리스트가 [0, 1, 1, 1, 1, 1, 1]이 되므로, 정답은 6이 됩니다.

접근 방법: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 윈도우 안에 포함된 0의 개수가 k 이하를 유지하면서, 윈도우의 최대 길이를 추적하는 방식입니다.

알고리즘 단계

• zeros := 0, ans := 0, j := 0으로 초기화합니다.
• nums의 각 인덱스 i와 값 n에 대해 다음을 반복합니다.
  • n이 0이면 zeros를 1 증가시킵니다.
  • zeros가 k보다 커지면, nums[j]가 0인 경우 zeros를 1 감소시키고 j를 증가시켜 윈도우의 왼쪽 경계를 오른쪽으로 이동합니다.
  • i - j + 1이 ans보다 크면 ans를 갱신합니다.
• 반복이 끝나면 ans를 반환합니다.

구현 예제

class Solution:
   def solve(self, nums, k):
      zeros = 0
      ans = 0
      j = 0
      for i, n in enumerate(nums):
         zeros += n == 0
         while zeros > k:
            zeros -= nums[j] == 0
            j += 1
         if i - j + 1 > ans:
            ans = i - j + 1
      return ans
ob = Solution()
nums = [0, 1, 1, 0, 0, 1, 1]
k = 2
print(ob.solve(nums, k))

입력

[0, 1, 1, 0, 0, 1, 1], 2

출력

6

복잡도 분석

각 원소는 윈도우가 확장될 때와 축소될 때 각각 한 번씩, 즉 최대 두 번 방문되므로 시간 복잡도는 O(n)입니다. 추가로 사용되는 변수가 몇 개뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다.